求解多集散点车辆路径问题的顺路捎带法
摘要:为了更好的解决多集散点车辆路径问题,文章突破了传统MDVRP研究中一个客户的订单只能由一辆车承载的限制,提出了一种新的算法.阐述了算法的基本原理,结合有效运输值,给出了算法具体的顺路捎带规则。
下载论文网 关键词:多集散点;车辆路径问题;顺路捎带法;有效运输 一、 引言 车辆路径问题(Vehicle Routing Problem VRP)是由Dantzig和Ramser于1959年首次提出来的,是运筹学、应用数学、网络分析、图论、计算机应用及交通运输等学科研究的一个热点问题,也是典型的NP难题.近年来,国内外学者对VRP的研究多集中在单车场的车辆路径安排上,较少关注多车场情况下的车辆路径问题。
多集散点车辆路径问题(Multi—Depot Vehicle Routing Problem,MDVRP)的解决方法比单车场条件下更加复杂,特别是当节点规模较大时,将很难得到问题的精确解.探讨如何经过少量计算,得到一个相对满意的解成为现阶段学者研究的重点.Polacek利用可变邻域搜索法(Variable Neighborhood Search)求解带时间窗的MDVRP;Laporte分别针对对称和非对称的多车场车辆路径问题提出来分支定界法;张明善等通过建立网络流模型,给出了网络流算法;钟石泉等对有容量、时间窗、多车型等约束条件的MDVRP给出了针对具体约束的禁忌算法(Tabu Search Algorithm);邹彤等对染色体编码进行改进,提出了能够表示每个车场所出动的车辆及其行驶路径的新的染色体编码,利用遗传算法(Genetic Algorithm,GA)解决了该问题;王素欣等建立以订单为基准的货运车辆路径问题模型,利用蚁群算法(Ant Colony Optimization,ACO)解决了该问题。
但是,通过分析我们不难发现,传统的多集散点车辆路径问题研究中,都限定每个客户的订单都必须且仅能由一辆车运送,这种限制在具体运输过程中是不现实的。
二、 MDVRP的模型 对于本文所要解决的多集散点车辆路径问题具体界定如下:某第三方物流公司在一段时间内有多项配送任务或订单需要完成.每项配送任务由配送的起点、终点、配送量构成。
如配送任务Rij(i,j,qij),其中i表示配送的起点,j表示终点,qij表示配送量。
要求合理安排行车路线,在完成配送任务的前提下使总的行驶距离最短。
根据以上描述,对MDVRP模型进行以下假设:①每项配送任务的配送量不超过车辆的最大载重量且车辆容量相同;②车辆行驶距离不能超过其最大行驶里程;③车辆完成所有配送任务后原地待命,不需要回到初始出发点;④每个集散点可由不同的车辆多次访问。
由以上分析建立模型如下: 目标函数: 其中i,j∈V,V为节点的集合;l∈NV,NV为车辆集合; X1ij表示编号为l的车辆是否从节点i载向节点j,如果是,X1ij=1,否则,X1ij=0;dij表示节点i,j间的距离;Qv为车辆最大载重量;q1j表示编号为l的车辆开往集散点j时车上货物的重量;Lmax为车辆行驶的最大里程数。
上述模型中,(1)将车辆总路径最小为优化目标;(2)、(3)分别表示配送量、车上货物重量不超过车辆的最大载重量;(4)车辆行驶距离不超过其最大里程数。
三、 顺路捎带法及有效运输 在以往的研究中,每个客户的订单都由一辆车独自完成。
在运输过程中,虽途经不同的节点,但是在到达配送任务的终点前,不允许中途卸货。
这种运输方式将每辆车都看作彼此之间相互独立的个体,个体之间独自完成配送任务,忽略了个体在运输过程中的合作关系。
顺路捎带法就是建立在车辆合作运输思想上的,通过一定方式的合作,车辆可以有效的提高满载率,减少运输距离,优化行驶路径。
所谓顺路捎带法是指,以合作运输为前提,不同的车辆在运输过程中,依据有效运输值的大小,将同一个订单的货物逐渐运送至离目标节点距离更近的节点上。
如有配送任务R12(1,2,q12)、R13(1,2,q13),同时在节点1有途经节点2的车辆k,若满足条件:(1)k有富余的运载能力,(2)距离d23 四、 仿真实验 某第三方物流公司在某一时刻的配送任务如表1所示,各节点坐标如表2所示.在这些节点中有的节点只运入货物,如节点1,11;有的节点只运出货物,如节点9,14;有的节点既有运入也有运出的货物,如节点6,7,10,并且节点7和10之间均有货物运送到对方。
假设车辆初始点分别为4,2,9,最大载重量QV=10t,出行最大里程Lmax=100km ,要求在不超载的情况下,合理安排车辆行车路线,以最小的成本完成所有配送任务。
用Java语言设计并实现,共进行40次运算,得到最小总路径长度为113.33km,所有配送任务由3辆车联合完成,各条路径的详细信息见表3。
在运输过程中,车辆依据有效运输值,动态的对订单进行顺路捎带,将订单的货物逐渐运送至距离目标节点更近的节点上,如订单R2,13(2,13,1.5)首先被车辆2捎带至节点7,然后被车辆1捎带至节点6,最后由车辆3运送至终点,完成该订单的配送;订单R10,5(10,5,3)先被车辆1捎带至节点7,然后由车辆3完成该订单的配送;订单R2,13(2,13,1.5)先被车辆1捎带至节点10,最后由车辆2运输至配送任务的终点。
五、 结论 重新描述了多集散点车辆路径问题的实际背景,用配送任务将货运关系清晰化;提出顺路捎带法,突破了一个客户的订单只能由一辆车运送的限制,提高了车辆的满载率,减少了车辆的行驶距离;量化了有效运输,给出了有效运输值的计算方法,为顺路捎带提供了依据。
参考文献: 1. Ramser D. The truck dispatching problem. Mgt Sci,1959,(6):81—89. 2. Polacek M, Hartl R F, Doerner K, et al. A variable neighborhood search for the multi depot vehicle routing problem with time windows. Springer Netherlands. Journal of Heuristics,2004,10(6):613—627. 3. 张明善,唐小我.多车场满载货运车辆优化调度的网络流算法.系统工程学报,2002,17(3):216—220. 4. 钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究.运筹学学报,2005,9(4):67—73. 基金项目:国家社会科学基金资助项目(07CTQ007)。
作者简介:牟小俐,重庆大学经济与工商管理学院副教授;唐纯金,重庆大学经济与工商管理学院硕士生。
收稿日期:2009—12—17。