当前位置：文档之家 › 带时间窗的车辆路径问题的精确算法研究

带时间窗的车辆路径问题的精确算法研究

  • 格式：doc
  • 大小：825.50 KB
  • 文档页数：8

龙源期刊网

带时间窗的车辆路径问题的精确算法研究

作者：答家瑞 郑澜波

来源：《物流技术》2017年第06期

[摘要]将CVRP（capacitated Vehicle Routing Problem）中的二维车流模型扩展至VRPTW中，用它来替代列生成算法中的分支一切割过程，为解决VRPTW提供了一种新思路。同时对最少车辆数量的理论上界进行了猜想，并用Solomon基准测试包进行了实验，求解出的算例均肯定了这一猜想。

[关键词]时间窗；车辆路径问题；运筹学；整数线性规划；列生成；精确算法

[中图分类号]F224.0 [文献标识码]A [文章编号]1005-152X（2017）06-0095-05

1引言

带时间窗的车辆路径问题（vehicle Routing Prob-lem with Time Windows，VRPTW）是对车辆路径问题的扩展，最早由Pullen在1967年提出，其主要不同点在于添加了一个时间窗来限制每个客户地点的服务时间，该限制可以针对于客户服务的最早开始时间、车辆停留在客户点的最短时间以及客户服务的最晚开始时间等，这些限制统称为时间窗约束。

VRPTW可以定义为一组车辆（V）一些客户（C）和一个有向图（G）。该有向图中包括|C|+2个点，其中客户点用1，2，…，n表示，仓库点用点0（开始点）和n+l（结束点）表示。用N来表示所有点的集合，A表示所有边的集合，即G（N，A）。对于每条边（i，j），cij表示该边上的行驶成本，tij表示途经该边的行驶时间。对于每个客户点i都有一个时间窗[ai，bi]，即到达i点的车辆最早开始服务时间为ai，最晚开始服务时间为bi，每个点的服务时间长度为sti，需要装载的货物重量（容量）为di。对于每辆车都有一个相同的载重量（最大容量）q。

2列生成算法

列生成（column generation）是一种求解大规模整数线性规划的方法。使用它进行求解时，不需要用到原始问题中所有的变量，而是求解一个子集（subset）。具体来说列生成通常会产生一个主问题，这个主问题的解依赖于一个或多个子问题的多重解（repeated solution）。

接下来用数学的方法来描述，我们用线性规划的方法定义主问题（master problem，MP），数学模型如下：

目标函数： 龙源期刊网

该模型相比于经典的三维多商品网络流模型，整数变量x减少了一维，但增加了一个线性变量u。提升该模型计算性能的关键在于如何降低K的上界，即至少需要多少辆车可以形成最优路径。在利用列生成算法解决基于集合划分的数学模型时，会得到线性主问题的下界（检验成本为0时），同时产生线性解中的路径数量值K'（该数量值可能不是整数），我们认为K'（向上取整）或K'+1（向上取整）很有可能就是K的理论上界，所以用该模型来替代列生成算法中得到主问题线性最优解后的分支一切割过程，以测试模型质量与最优性。

4带资源约束的基本最短路径问题

带资源约束的基本最短路径问题（ElementaryShortest Path Problem with Resource

Constraints，ESP-PRC）是VRPTW基于列生成算法的子问题。当用集合划分模型作为主问题，利用列生成算法来解决VRPTW时，子问题被分解成多个性质相同的ESPPRC。更加明确地来说，子问题是一个带时间窗与容量约束的基本最短路径问题（Elementary Shortest Path

Problem withTime Windows and Capacity Constraints，ESPPTWCC），其中“基本”（elementary）的意思是每个客户点只能出现一次，即最优解中不存在回路（cycle）。

本文基于整数线性规划，加入以下三组有效不等式对子问题进行了建模求解。

4.1点边不等式

5实验结果

实验数据来自于经典的Solomon基准测试包，测试包中的数据集合分为三类，

r组：客户点坐标呈随机分布；

c组：客户点坐标呈现分块聚集分布；

rc组：客户点坐标既有随机分布又有分块聚集分布。

每个算例都包括100个客户点、50个客户点和25个客户点三种规模，后两种分别是取包括100个客户点的完整算例中的前50个和25个客户点。

计算实验都是在含有2.5GHz的Intel（i7-4710MQ）处理器、12GB内存以及配有64位Windows操作系统的戴尔一体机上运行。使用Java（编译版本1.7）在Eclipse上进行算法编译，借助IBM Ilog cplex/Concert 12.6进行建模优化。

主问题：基于集合划分的数学模型；

子问题：加入三种有效不等式后的整数线性规划模型。 龙源期刊网

得到主问题的下界后用基于二维车流的数学模型求最优解，该方法简称为ILP算法。

ILP算法是通过在Hog Cplex中的Cplex优化器上建立列生成结构与数学模型进行求解，Cplex参数设置为默认。

实验在求解完所有子问题得到主问题的下界后，会得到一个线性解中的路径数量值K'，我们将二维车流模型中的K（所需的车辆数量或路径数量）定义为整数变量，其取值范围设置为[K'，K’+1]，直接求解该模型，输出最优解。为了测试修改后二维车流模型的性能，我们不会将下界加入到模型中去。

目前Solomon基准测试包对于我们的算法过于困难，仅选择其中25个客户点的数据进行测试，以验证修改后的二维车流模型的性能。

表中具体说明如下：

LB：下界（Lower Bound），空白格代表500秒内未求解出下界；

Opt：最优解（Opimal solution），空白格代表500秒内未求解出最优解；

Num：子问题的迭代次数，即求解了Num个子问题；

Paths：产生的路径数量之和，即加入到主问题中列（column）的数量；

LBT：求解到下界的时间，单位是s；

OptT：修改后二维车流模型的求解时间，单位是s；

TT：总时间（Total Time）。

在表1、表2和表3中，可以看出在求解出下界后，用修改后的二维车流模型来求解得最优解的时间表3 c组25个点的VRPTW测试结果（OptT）非常短，可以认为它能够替代列生成算法后期的分支一定界部分。在目前求解出的所有算例中，二维车流模型的解与前人提供的最优解相同，但由于尚未求解出更多的算例，无法肯定K'+1（向上取整）就是K（最优解中的路径数量）的理论上界，目前的结果都倾向于肯定这一猜想。

6结束语

带时间窗的车辆路径问题是经典的组合优化问题，也是目前应用最广泛的运输问题之一，具有很高的研究价值。国内的研究往往倾向于用启发式方法解决该问题，精确算法的研究非常匮乏。对于启发式方法，我们认为它最大的优势在于高效性和通用性，而这也在一定程度上导龙源期刊网

致了它精确性的不足。针对一个NP-hard问题，如果没有透彻的理论分析和精确算法做支撑，就很难建立适合的启发式算法，更不能保证其求解质量。

我们将CVRP中的二维车流模型扩展至VRPTW中，用它来替代列生成算法中得到主问题线性最优解后的分支一切割过程，为解决VRPTW提供了一种新思路。

龙源期刊网

龙源期刊网

龙源期刊网

龙源期刊网

合集下载

带时间窗车辆路径问题的并行遗传算法

带时间窗车辆路径问题的并行遗传算法

第１０卷第３期　２００７年５月　工业工程　Ｉｎｄｕｓｔｒｉａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｊｏｕｒｎａｌ　Ｖｏ１．１０　Ｎｏ．３　Ｍａｙ　２００７　带时间窗车辆路径问题的并行遗传算法　张智海，吴星玮　（清华大学工业工程系，北京１０００８４）　摘要：采用并行遗传算法研究了带时间窗限制的车辆路径问题。通过设计并行算法和交叉、变异等算子提高了算法　的计算效率和性能。通过计算若干ｂｅｎｃｈｍａｒｋ问题，验证了模型的有效性。　关键词：带时间窗车辆路径问题；并行遗传算法；组合优化　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１００７—７３７５（２００７）０３－０１１１－０４　Ｐａｒａｌｌｅｌ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ　ｗｉｔｈ　Ｔｉｍｅ　Ｗｉｎｄｏｗ　ＺＨＡＮＧ　Ｚｈｉ—ｈａｉ．ＷＵ　Ｘｉｎｇ—ｗｅｉ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｄｕｓｔｒｉａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ　１０００８４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｏ　ｓｏｌｖｅ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ｔｉｍｅ　ｗｉｎｄｏｗ，ｐａｒａｌｌｅｌ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｉｎ　ｔｈｅ　ｐａｐｅｒ．Ｃｏｍｐｕｔｉｎｇ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ａｌｇｏｒｉｔｈｍ　ａｒｅ　ｉｍｐｒｏｖｅｄ　ｂｙ　ｄｅｓｉｇｎｉｎｇ　ｐａｒａｌｌｅｌ　ａｌｇｏ—　ｒｉｔｈｍ，ｃｒｏｓｓｏｖｅｒ　ａｎｄ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒｓ．Ｖａｌｉｄｉｔｙ　ｏｆ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｃｏｎｆｉｒｍｅｄ　ｂｙ　ｓｏｌｖｉｎｇ　ｓｏｍｅ　ｂｅｎｃｈｍａｒｋ　ｐｒｏｂｌｅｍｓ．　Ｋｅｙ　ｗｏｒｄｓ：ＶＲ唧：ｐａｒａｌｌｅｌ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｃｏｍｂｉｎａｔｉｏｎ　ｏｐｔｉｍｉｚａｔｉｏｎ　车辆路径问题（ＶＲＰ）是指对一系列发货点／收　货点，组织适当的行车路线，使车辆有序地通过他　们，在满足一点的约束条件（如货物需求量、发送量、　交货时间、车辆容量限制、行驶里程限制、时间限制　等）下，达到一定的目标（如路程最短、费用极小、时　间最少、使用车辆尽量少等）Ｌ１　，Ｄａｎｔｚｉｇ和Ｒａｍｓｅｒ　于１９５９年首次提出后　Ｊ，很快便引起运筹学、应用　数学、图论与网络规划、计算机应用科学领域专家的　重视，取得了一系列重要的成果，并在实际应用中获　得了显著的经济效益。　车辆路径问题的求解方法基本上可分为精确算　法和启发式算法。由于ＶＲＰ是一个ＮＰ—ｈａｒｄ问题，　因此大量研究集中在设计有效的启发式算法上Ｌ２引。　其中算法的计算速度和求解精度是启发式算法研究　的重点。各种车辆路径问题中，带时间窗的车辆路　径问题由于在实际中具有广泛的应用，因此得到了　深入的研究　。Ｊ，遗传算法、模拟退火算法、蚁群算法　等是常见的几种方法。研究主要通过寻找问题域特　征并结合局部搜索算法，实现ＶＲＰＴＷ问题的求解，　但计算精度与效率上距实际需求还存在很大距离，　因此采用先进计算技术与启发式算法联合求解是另　一研究热点　Ｊ。本文采用并行遗传算法研究了　ＶＲ唧。通过与若干ｂｅｎｃｈｍａｒｋ问题的比较，验证　了模型的有效性。　１　ＶＲＰＴＷ的数学模型　车辆路径问题可以用图论方法来描述。设Ｇ＝　（　，Ａ）为一个完全图，其中Ｖ＝｛０，…，ｎ｝是顶点集，　Ａ是由所有的弧组成的集合。顶点ｉ＝１，…，ｎ表示　收货点，顶点０表示发货点。与弧（ｉ，＿『）相对应有一　个非负的费用ｃ　表示由收货点ｉ到收货点　的费　用。在此基础上，ＶＲＰＩ＇Ｗ添加了时间窗约束，即每　个收货点都有一个允许服务时间范围，它是一个典　型的带约束组合优化问题，并被证明为ＮＰ．ｈａｒｄ问　收稿日期：２００５．１１—２８　基金项目：深圳物流中心基金资助项目　作者简介：张智海（１９７４．），男，湖南省人，讲师，

带时间窗的冷链物流车辆路径优化问题研究

带时间窗的冷链物流车辆路径优化问题研究

龙源期刊网

带时间窗的冷链物流车辆路径优化问题研究

作者：徐松梅

来源：《物流科技》2017年第09期

摘 要：文章研究了带有硬时间窗限制的超市速冻食品冷链配送车辆路径优化问题，根据其配送批量小，配送地点分散，时间要求高的特点建立了配送成本最小的目标函数，以降低物流的配送成本，提高其经济效益。该模型考虑了配送过程中的固定成本、运输成本、时间惩罚成本以及制冷成本，其配送车数、每两个客户间的运输量、配送时间以及卸货时间相互作用，共同影响总成本，然后采用遗传算法求解，最后以一个物流公司为算例，进行求解证明该模型的可行性。

关键词：路径优化；冷链物流；遗传算法

中图分类号：U116.2 文献标识码：A

Abstract： In this paper， we study the optimization of the problem of the cold chain

distribution of the frozen food in the supermarket with the hard time window. According to the

characteristics of the small batch distribution， the scattered distribution time and the high time

requirement， the objective function of the minimum distribution cost is established to reduce the

distribution of the logistics cost， improve its economic efficiency. The model takes into account the

有时间窗的车辆路径问题及改进禁忌搜索算法

有时间窗的车辆路径问题及改进禁忌搜索算法

第４９卷第１期　２０１１年１月　吉林大学学报（理学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．４９　ＮＯ．１　Ｊａｎ　２０１ｌ　

有时间窗的车辆路径问题及改进禁忌搜索算法　

葛金辉　

（通化师范学院数学系，吉林通化１３４００２）　

摘要：基于改进的禁忌搜索算法求解有时间窗的车辆路径问题，建立了该问题的通用数学模　

型．改进算法中，在随机构造的多个可行解中挑选较好的解作为初始解，采用２－ｏｐｔ方法生成　邻域，并构造了动态禁忌表，使禁忌表的大小和结构随搜索过程发生改变，提高了整体寻优　

能力．仿真实验证明了算法的可行性、有效性和优越性．　

关键词：车辆路径问题；禁忌搜索算法；时间窗　中图分类号：ＴＰ１８　文献标志码：Ａ　文章编号：１６７１－５４８９（２０１１）０１－０１０５－０７　

Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ　ｗｉｔｈ　Ｔｉｍｅ　Ｗｉｎｄｏｗｓ　ａｎｄ　

Ｉｍｐｒｏｖｅｄ　Ｔａｂｕ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ　

ＧＥ　Ｊｉｎ—ｈｕｉ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆＭａｔｈｅｍａｔｉｃｓ，Ｔｏｎｇｈｕａ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｔｏｎｇｈｕａ　１３４００２，Ｊｉｌｉｎ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｎ　ｉｍｐｒｏｖｅｄ　ｔａｂｕ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｕｔｉｌｉｚｅｄ　ｔｏ　ｓｏｌｖｅ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ｔｉｍｅ　ｗｉｎｄｏｗｓ　ａｎｄ　ｂｕｉｌｔ　ａ　ｇｅｎｅｒａｌ　ｍａｔｈｅｍａｔｉｃａｌ　ｍｏｄｅｌ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｔｏ　ｔｈｉｓ　ｐｒｏｂｌｅｍ．Ｉｎ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｏｆ　ｓｏｌｖｉｎｇ，ｉｎｉｔｉａｌ　

ｓｏｌｕｔｉｏｎｓ　ｗｅｒｅ　ｓｅｌｅｃｔｅｄ　ｆｒｏｍ　ｍａｎｙ　ｒａｎｄｏｍ　ｓｔｒｕｃｔｕｒｅｄ　ｐｒａｃｔｉｃａｌ　ｓｏｌｕｔｉｏｎｓ．ａｎｄ　２一ｏｐｔ　ｍｅｔｈｏｄ　ｗａｓ　ａｄｏｐｔｅｄ　ｔｏ　ｐｒｏｄｕｃｅ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｄ　ｓｔｒｕｃｔｕｒｅｄ　ｄｙｎａｍｉｃ　ｓｔｒｕｃｔｕｒｅ　ｔａｂｕ　ｌｉｓｔ　ＳＯ　ｔｈａｔ　ｔｈｅ　ｓｉｚｅ　ａｎｄ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｔａｂｕ　ｌｉｓｔ　ｃｏｕｌｄ　

带时间窗车辆路径问题的粒子群算法

带时间窗车辆路径问题的粒子群算法

2004年4月系统工程理论与实践第4期　

文章编号:100026788(2004)0420130206

带时间窗车辆路径问题的粒子群算法

李　宁1,2,邹　彤1,孙德宝1

1.华中科技大学控制科学与工程系,湖北武汉430074;2.武汉理工大学计算机科学与技术学院,湖北武汉430070)

摘要:　将粒子群算法(PSO)应用于带时间窗车辆路径优化问题(VRPTW),构造车辆路径问题的粒子表达方法,建立了此问题的粒子群算法,并与遗传算法作了比较Λ实验结果表明,粒子群算法可以快速、有效求得带时间窗车辆路径问题的优化解,是求解带时间窗车辆路径问题的一个较好方案Λ关键词:　车辆路径问题;粒子群算法;优化中图分类号:　O221.1;U116.2 文献标识码:　A

ParticleSwarmOptimizationfor

VehicleRoutingProblemwithTimeWindows

LINing1,2,ZOUTong1,SUNDe2bao1

(1.DepartmentofAutomaticControl,HuazhongUniversityofScience&Technology,Wuhan430074,China;2.SchoolofComputerScience&Technology,WuhanUniversityofTechnology,Wuhan430070,China)

Abstract:　Thispaperintroducesaproposaltoextendtheheuristiccalled“ParticleSwarmOptimization”(PSO)todealwiththeVehicleRoutingProblemwithTimeWindows(VRPTW),andproposesanovelParticlepresentationforthevehicleroutingproblem.ThePSOiscomparedwithGAinthesameVRPTWinexperiments.ExperimentalresultsindicatethatthePSOcaneffectivelyandquick2lygetoptimalresolutionofVRPTW,soitisprovedtobeaneffectivemethodforVRPTW.Keywords:　vehicleroutingproblem;particleswarmoptimization;optimization