logo资料库

配送中心两点间的多目标最优路径问题建模和优化.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.04M 资料格式：doc 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    配送中心两点间的多目标最优路径问题建模和优化
    配送中心两点间的多目标最优路径问题建模和优化 作者：刘根生 皋古之 2010-09-27 一：课题的意义： 物流作为一种经济活动，随着商品经济发展而形成。在经济日益全球化的今天，现代物 流作为“第三个利润源泉”正受到日益广泛的重视，并面临着前所未有的发展机遇。现代物流 已经贯穿于我国生产、分配、流通和消费的各个领域，社会对物流需求的数量、质量正在不 断提高，这些都为我国物流与国际物流接轨并融入全球物流一体化提供了条件。 物流配送在物流系统中扮演着重要的角色，是物流顺利实施的根本保障，畅通、高效的 物流不但可以提高货物周转效率，还能通过规模优势有效降低物流成本、减少企业库存，从 而提高企业经济效益。 物流信息是物流管理的基础，计算机技术的应用加速了信息的获取，缩短了物流的活动 周期。设计高效实用的物流配送算法、应用高速发展的计算机系统为物流配送系统实现合理 路径运输,从而节约运输时间、减少运输费用, 提高现代物流系统效率和降低成本非常必要。 本课题通过深入学习现有的模型算法，借鉴已有的数学模型，并根据城市配送中心的实 际需求，建立城市配送中心两点间的多目标最优路径问题模型，并在建模的基础上，借助运 筹学路网中的最短路径算法和前 k 条简单路径的算法对模型求解，帮助用户找到满足自己 需要的最优路径。 二: 最优路径问题研究现状 最优路径问题是人们长期研究的问题，在物流配送和选址、城市交通、车辆导航系统以 及 GIS 领域等方面有广泛的应用。 配送的目标之一就是以最小的代价，将产品从原产地（或物流配送中心）转移到规定地 点。因此，制定车辆调配计划和配送路线计划就显得非常重要了。一般说来，最小的代价所 对应的配送路径就是最优路径。 最优路径绝不等同于最短路径。在物流配送过程中，最短路径，无论是时间最短还是距 离最短，都不一定是行车意义上的最优。最优路径需要考虑许多因素：有的用户关注运输距 离，有的用户关注送货时间，而道路通行状况（道路是否平坦、有没有时间窗、交通状况等） [2]也是每个用户必须考虑的。由此可见不同用户对配送的要求不可能完全相同，因而他们 对最优的理解也不尽相同。 以往有关最优径算法的研究大部分集中在最短路径上，而不一定是用户需求意义下的 “最优”路径。主要是因为最短路径相对于最优路径，人们研究得较早，容易建立数学模型，
    模型相对简单，算法也比较成熟。最短路径是最优路径的基础，大多数最优路径都是通过解 决最短路径来实现的。 最短路径的算法比较成熟。较为出名的算法有 Dijkstra 算法、逐次逼近算法和 floyd 算法等等。其中 Dijkstra 算法是公认的解决网络中两点间最短路径的最好算法。 从 Dijkstra 算法诞生到现在，人们对他进行了很多的改进[3]，以适应越来越庞大的网 络体系。改进主要表现在两个方面[4]： 在对临时标号点的排序问题上选取堆排序，大大降低了数据比较的频率。堆排序的主要 运行时间消耗在建初始堆上,而对于 Dijkstra 算法来说,整个最短路径的搜索过程中进行的 n 次堆排序只需要建一个堆，从而明显克服了堆排序的主要缺点，使堆排序的优势更加明显 地发挥出来。 对于搜索的改进。我们知道 Dijkstra 算法的搜索是一种无序的没有方向的搜索，怎样 把这种没有方向的搜索变得“有向”？基于 Dijkstra 算法的 A*算法就是基于此而提出的。 对于几何路网来说，将临时标记结点到源点的最短路径与本临时标记结点到目标结点的 直线距离之和作为此临时标记结点的一个属性值，这个属性值将作为从临时标记结点集合中 选取永久标记结点的依据, 即选取此属性值最小的临时结点作为永久标记结点，这种优化方 法称为直线优化 Dijkstra 算法。王开义、赵春江等人把这种方法用于 GIS 领域[4]。 现在，人民已经成功地把两点间的最短路径算法应用在 GIS 领域[5][6]、配送中心选 址[7]、城市交通网络[8][9][10]、车辆导航系统[2]以及电子商务物流[11]等领域中。这 些文献所用的两点间的最短路径算法大都是 Dijkstra 算法。 值得一提的是，人们对最短路径的研究，大多数集中于路段权值固定的情况。对于路段 权值是随机变量（比如权值代表车辆通过的时间）的情况，研究得不如路段权值固定的情况 透彻。 然而，各个权值意义下的最短路径不一定能满足用户的要求。用户对最优的理解往往是 建立在多种因素之上的，甚至有的因素难以量化。多目标意义上的最优路径才是最佳的选择。 苏一丹、李桂等人对各种最优路径进行分类[11]，其分类如下： 图 2.1 最优路径分类 从上表可以看出，除了加权综合最优路径考虑多种目标权值之外，其余最优路径也就是 单纯的最短路径。其静态型最优路径的目的是给不同的用户以不同的最短路径（加权综合最 优路径除外，这里的最短是广义的，不只局限于距离）。论文的结果也没有综合考虑各种单 目标最优路径情况，因而难以说明是多目标最优路径问题。但是已蕴含了多目标最优路径问 题的雏形。 三：前 k 条简单最短路径问题
    前 k 条最短路径问题是人们长期研究的问题，它是最短路径的推广。事实求是地说， 国外在这方面的研究是领先于我国国内的。国外不仅有许多创新性的论文，而且还拥有象 D.Eppstein 、J.Y.Yen 以及 John Hershberger 这些在这一领域卓有成就的专家和学者。 给定一个有向图(DG, directed graph)G=(V,E)，其顶点数 n=|V|，边数 r=|E|，G 中没有负权边，再给定一个正整数 k 和两个顶点 s 和 t，按照升序求出从 s 到 t 的前 k 条最 短路径。在前 k 条最短路径问题中，要找的不只是一条路径，而是多条路径，而且这多条 最优路径按照升序排列。前 k 条最短路径问题可分为有简单约束和没有简单约束两大类。 所谓的简单路径就是指不含有圈的路径，也就是不能重复走点的路径。下图说明了前 k 条 最短路径与前 k 条简单最短路径的区别[12]： 图 3.1 前 k 条最短路径与前 k 条简单最短路径的区别 从上图中我们可以看出，前三条简单最短路径的长度分别为 5，30 和 30。而没有简单 约束的前三条最短路径为 5，7 和 9，路径中可以有圈（5，6，5）。可见，尽管在一个非 负权值图中，最短路径总是简单路径，但是第二、第三……最短路径中可能有圈。 相对于没有简单约束的前 k 条最短路径问题，前 k 条简单最短路径问题更有挑战性。 最早的算法是由 Hoffman and Pavley[13]与 1959 年给出。较有名的结果是由 J.Y.Yen[14][15]于 1971 年提出，他的算法使用了现代数据结构，这个算法的时间复杂度 为 O(kn(m+nlogn))。这个算法里，每输出一次所需路径，要执行 O(n)次单一源点的最 短路径（第一条路径，即最短路径除外）。 2003 年，John Hershberger、Matthew Maxel 和 Subhash Suri[12] 等人提出 了新的算法，这个算法和 Yen 的算法不同之处在于新的算法先根据已得出的前 i 条最优路 径建立路径分支结构，然后根据路径分支结构把待选路径（前 i 条最优路径之外的路径集合） 分为好多的等价类。在每个等价类中，他们使用 John Hershberger 和 Subhash Suri 提 出的新的替代路径(Rplacement Paths)算法[16][17]。本算法的时间复杂度也为 O(kn(m+nlogn))。根据 John Hershberger 等人的试验结果，在大多数情况下，这种算 法比 Yen 的算法快。但是，诚如 John Hershberger 等人在其论文中指出的那样，在有向 图的情况下，他们的替代路径算法有时候会失效，不过这种失效容易监测得到。一旦出现替 代路径算法失效,就在这一轮里使用别的替代路径算法。 我们课题关注的是前 k 条简单最短路径。这与我们物流的优化目标是分不开的。 图 3.2 带圈的第 i 条最短路径 在图 3.2 中，假设我们的优化目标是距离，从点 1 到点 6 没有简单约束的第 i 条最短 路径为：PathA={e<1,2>,e<2,3>,e<3,5>,e<5,4>,e<4,3>,e<3,6>}。由于点 3 被经过两次，显然这是一个带圈的路径。删除边 e<3,5>，e<5,4>和 e<4,3>后，我们
    得到一个简单的路径 PathB={e<1,2>,e<2,3>,e<3,6>}。容易证明 PathB 的长度小于 PathA 的长度，即 PathB 是从点 1 到点 6 前(i-1)条最短路径中的一条，而 PathA 是从点 1 到点 6 第 i 条最短路径。不仅从距离的角度来讲，PathB 优于 PathA，就是从时间或成 本的角度来讲，PathB 亦优于 PathA，因为 PathB 中的路段 PathA 也全部经过。可见， 我们求出了 PathB 之后，就没有必要再求出 PathA 了。基于这个原因，我们主要关注有简 单约束的前 k 条最短路径。 四:配送中心两点间的多目标最优路径问题模型 配送中心两点间的多目标最优路径问题模型如下： 图 4.1 配送中心两点间的多目标最优路径问题模型 模型描述：在一个有向图 G=(V,E)中，有 n 个顶点，r 条有向边。若两点之间有有向 边连接，表示从边的 tail 点可以不经过其它的点直接到达边的 head 点。比如图 6.1 中， 有一条边 e<8,2>,表明从点 8 可以直接到达点 2。而图中没有边 e<2,8>，表明从点 2 不 可以直接到达点 8。对于每条边按照规定的顺序（比如，都按照路段长度、车辆通过此路段 的时间、车辆通过此路段所需成本）赋给多个目标权值。路径的目标权值是其经过的所有路 段的目标权值之和。求图中任意两点间满足一定客户多目标需求的最优路径。 五：多目标最优路径的实现方法 对于配送中心两点间的多目标最优路径问题我们可以采用以下三种办法： 1. 方法一：路段权值单一化法。这种方法赋给每一路段一个单一的固定的权值，只不 过这个权值不只考虑了距离，也不只考虑时间，而是考虑多种因素。然后利用综合权值作为 key 目标权值，调用两点间的最短路径算法，把得到的最短路径作为最优路径。值得指出的 是，如何计算路段的综合权值对这种方法来讲是个值得探讨的问题。 2. 方法二：以路段的某一个目标权值作为 key 目标权值，求出两点间的前 k 条简单最 短路径。然后把这 k 条路径的各目标权值计算出来。比如我们赋给有向图的各路段三个权 值，三个权值分别代表路段的距离、路段的通行时间以及路段通行成本。我们以路段的距离 为目标权值求出前 k 条最短路径，然后把这前 k 条最短路径的距离、通行时间和通行成本 计算出来。用户可以根据自己的实际需求综合路径的各目标权值从这前 k 条路径中选择一 条路径作为最优路径。 为了用户使用方便，我们可以把计算结果列入表格。以距离为 key 目标值的前 K 条最 优路径的各目标权值的表格如下： 表 5.1 某一目标权值作 key 目标权值所得到的路径及其各目标权值 路径路径长度（key 权值）通行成本通行时间均值通行时间方差 Path1
    Path2 ……… Pathk 3. 方法三：路段的各个目标权值轮流作 key 目标权值，分别求出前 k 条简单最短路径。 若每个路段有 m 个目标值，那么就可以得出 mk 条路径,然后把这 mk 条路径的各目标权值 计算出来。用户可以根据自己的实际需求综合路径的各目标权值从这前 mk 条路径中选择 一条路径作为最优路径。假设我们赋给有向图的各路段三个权值，三个权值分别代表路段的 距离、路段的通行时间以及路段通行成本。我们就可以得到这 3k 条路径的距离、通行时间 以及通行成本仿照方法二，我们把方法三的计算结果列入表格。 表 5.2 各目标权值轮流作 key 目标权值所得到的路径及其目标权值 key 目标权值路径路径长度通行时间均值通行时间方差通行成本 路径长度 Path1 ……… Pathk 通行时间均值 Path1 ……… Pathk 通行成本 Path1 ……… Pathk 六：两点间的多目标最优路径问题方法选择 上文提出了解决配送中心两点间的多目标最优路径问题模型的三种方法。我们选择哪种 方法呢？ 方法一不仅算法简单，而且其给出的最短路径就是最优路径。但是在赋值时是综合赋值， 由于各目标权值的单位是不同的，综合权值与各目标权值的关系函数难以确定。而且客户的 需求是多样的，不同的客户、不同的时间会有不同的需求，固定系数显然是不符合现实的。 这种算法更多地依赖客户的经验，有时需要用户不断根据反馈信息对综合权值与各目标权值 的关系函数作调整。 方法二和方法三根据路段的目标权值分别给出了 k 条和 mk 条最优简单路径，并给出 每条路径相关的权值，其算法有理有据，使人信服，并且到底哪条是用户心中的最优路径并 不是由算法给出，而是用户根据计算结果自己做选择。
    但是方法二和方法三还是不同的。方法二只以路段的一个目标权值作为 key 目标权值 求备选路径，而方法三把路段的各目标权值平等对待，充分利用了现有数据。再者，假设客 户要求给出 y 条备选路径，方法二要以某一目标权值为 key 目标权值求出前 y 条简单最短 路径，而方法三只要算 m 次前([y/m]+1)条简单最短路径（[y/m]表示不超过 y/m 的最 大正整数）。在算法上，方法二比方法三有更复杂的时间复杂度。 在现实的物流配送中，给出八到九条备选路径就已经能满足用户的需求了。假若我们各 路段有三个目标权值，要求给出九条备选路径,我们只要分别以这三个目标权值分别作 key 目标权值求出前三条简单最短路径即可。我们总共计算了三次（第一）最短路径、三次第二 简单最短路径和三次第三简单最短路径就可以了。 七：算法实现及其结果 我们这里选择方法三来实现配送中心两点间的最优路径。 7.1 数据来源和程序运行环境 道路图片来源于 google earth 上美国某城市的地图。我们选择了 83 个点和 288 条路 段，对其各路段的各个目标权值进行了相关的处理，处理结果使得每个路段有四个值：路段 长度、路段通行成本、路段通行时间的均值和方差。在这里，我们把路段的长度和车辆通过 某路段的成本作为固定值，而车辆通过某路段的时间是一个正态的随机变量。分别以路段长 度、路段通行成本和路段通行时间的均值轮流做 key 目标值求得前三条简单最短路径。本 课题假定各道路的通行时间是不相关的。这样便于在求得九条路径之后估计各路径通行时间 的方差。 程序运行的计算机环境如下： 1. 操作系统：Microsoft Windows XP Professional 2002 Service Pack 2 2. CPU：Pentium(R) 4 CPU 2.8GHz 3. 内存：512MB 编译器：Dev C++ Version 4.9.9.2。 7.2 程序运行结果 本程序可以算出图中任意两点间的各目标权值下的前 3 条最短路径，一共输出 9 条路 径。各路径所经过的点及其相关的目标权值如下： 图 7.1 程序运行结果截图 我们看到，程序不仅给出了 9 条路径，而且给出了各路径的路径长度、通行成本、通 行时间的均值和方差。为了方便用户进行路径选择我们把程序的运行结果绘制成下面的表 格： 表 7.1 路径目标权值信息表
    key 目标权值路径路径长度 （米）通行成本 （分）通行时间均值 （秒）通行时间方差 （秒 2） 路径长度 Path1 4083 736 693 1077 Path2 4113 741 692 1154 Path3 4125 737 699 1082 通行成本 Path1 4083 736 693 1077 Path2 4125 737 699 1082 Path3 4150 741 700 910 通行时间均值 Path1 4113 741 692 1154 Path2 4083 736 693 1077 Path3 4125 737 699 1082 我们也可以把各路径在原图上标出来，方便用户考虑一些难以量化的路段信息。下面的 三张图分别是前三条距离最短路径示意图、前三条成本最短路径示意图和前三条时间均值最 短路径示意图。其中红色为最短路径，蓝色为第二最短路径不同于最短路径的部分，黑色为 第三最短路径不同于第一、第二最短路径的部分。 图 7.2 前三条距离最短路径示意图 图 7.3 前三条成本最短路径示意图 图 7.4 前三条时间均值最短路径示意图 八.结果处理和使用 在路径目标权值信息表，虽然给出了九条备选路径，但是，我们看到，有好多路径是重 复的。比如距离最短路径、通行成本最短路径和通行时间均值第二简单最短路径是同一条路 径，在最终的结果处理时，理所当然地可以把这三条备选路径当作揖条路径来处理。若每个 路段有 m 个权值，每个权值求前 k 条简单最短路径，那么可得出 mk 条备选路径，当相同 的备选路径合并后，可以得出的最终备选路径数在 k 和 mk 之间。 不同的用户有不同的第一、第二、第三目标。下面我们根据第一目标的不同把最终备选 路径列入下列表格： 表 8.1 最终路径目标权值信息表（路径长度为第一目标） 路径路径长度 （米）通行成本
    （分）通行时间均值 （秒）通行时间方差 （秒 2） Path1 4083 736 693 1077 Path2 4113 741 692 1154 Path3 4125 737 699 1082 Path4 4150 741 700 910 表 8.2 最终路径目标权值信息表（通行成本为第一目标） 路径通行成本 （分）路径长度 （米）通行时间均值 （秒）通行时间方差 （秒 2） Path1 736 4083 693 1077 Path2 737 4125 699 1082 Path3 741 4113 692 1154 Path4 741 4150 700 910 表 8.3 最终路径目标权值信息表（通行时间均值为第一目标） 路径通行时间均值 （秒）通行时间方差 （秒 2）路径长度 （米）通行成本 （分） Path1 692 1154 4113 741 Path2 693 1077 4083 736 Path3 699 1082 4125 737 Path4 700 910 4150 741 我们看到由于不同的 key 目标权值在求前 k 条简单最短路径上有路径重复的现象，尽 管初步求得的备选路径有 mk 条，但是最终的备选路径却很少。为了增加最终备选路径的 数目，使得用户在最终决策时可以考虑更多的非定量因素，当出现最终备选路径数目很少的 时候，我们可以在 m 不变的情况下加大 k 的数目，以使得最终输出的备选数目符合用户的 需求。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料