单车独占性带时间窗口装卸货问题的分析与算法

第39卷第3期 2005年3月 上 海 交 通 大 学 学 报 JOURNAL OF SHANGHAI JIAOTONG UNIVERSITY Vol. 39 No. 3 Mar. 2005 文章编号:1006-2467(2005)03-0409-04 单车独占性带时间窗口装卸货问题的分析与算法 贾永基， 谷寒雨， 席裕庚 (上海交通大学 自动化研究所，上海 200030) 摘 要:提出了一类广泛存在于运输领域的NP-hard组合优化问题— 独占性带时间窗口装却货 (E-PDPTW)问题，给出了它的数学描述，分析了其性质并把问题简化为不对称带时间窗口旅行商 问题(TSP)，提出了求解单车E-PDPTW 问题的两阶段快速算法，其时间复杂度只有O(n3),测试 结果表明了该算法的有效性和快速性， 关键词:装却货问题;时间复杂度;独占性;时间窗口 中图分类号:TP 301 文献标识码:A Analysis and Algorithm of Single一Vehicle Exclusive Pickup and Delivery Problem with Time Windows HA Yong-ji， GU Han-yu， XI Yu-geng (Inst. of Automation，Shanghai Jiaotong Univ.，Shanghai20003O，China) Abstract:The exclusive pickup and delivery problem with time windows (E-PDPTW )，an NP-hard combi- natorial optimization problem existed extensively in the transportation domain，was proposed. The mathe- matical description of this problem was proposed and its properties were analyzed，and then the problem was simplified as an asymmetric traveling salesman problem (TSP) with time windows. A two-phase quick algorithm to solve single vehicle E-PDPTW was proposed，whose time complexity is only 0(n')and the test results indicate the algorithm is effective and quick. Key words:pickup and delivery problem(PDP);time complexity;exclusive;time windows 带时间窗口装卸货问题(PDPTW)是一类在运 输领域中具有广泛应用的NP-hard组合优化问 题川.通常情况下，这类问题的规模较大，解决它相 当困难.近20年来，PDPTW 问题的研究出现了很 多有意义的成果[[1- 4]，但是仍然存在需要深人探讨 的领域和问题. 独占性带时间窗口装卸货问题(E-PDPTW)是 一类特殊的PDPTW 问题，在该问题中，一旦车辆 开始服务某客户，一直到把货物运到该客户的目的 地为止，中间不允许服务别的客户，即客户对于正在 为他服务的车辆具有独占性.如果一辆车能服务所 有客户则称为单车E-PDPTW问题;如果由多辆车 来满足所有客户的运输要求，则称为多车 E- PDPTW问题.本文研究的是单车E-PDPTW 问题， 阐述了其数学描述，并在分析问题性质的基础上，给 出了求解该问题的快速、有效算法. 1 E-PDPTW问题的数学描述和性质 1.1 E-PDPTW问题的数学描述 设G是所有客户的集合，n是G中客户的数目. 收稿日期:2004-03-04 基金项目:国家自然科学基金资助项目(60274013) 作者简介:贾永基(1976-)，男，山东烟台人，主要从事复杂系统优化算法研究.席裕庚(联系人)，男，教授，博士生导师， 电话(Tel. ):021-62933155;E-mail:ygxi@sjtu. edu. cn. 万方数据 上 海 交 通 大 学 学 报 第39卷 每一个客户都指定一个装货点和一个卸货点，因此 装、卸货点的个数都为n.设客户i的装货地点为 P;，卸货地点为D、，车库则为点0.设点i的时间窗 口为〔a; ,b;](a镇b;) ,a*和b、分别是该点最早和最晚 的服务时刻，即点i只能在此时间窗口内接受服务 (其中a。是车库的最早开始时刻，b。是车库的最晚 结束时刻).对于两个不同的点i, j, t;,，和c; ,，分别代 表从点i到点j的运输时间和运输代价. 在E-PDPTW问题中，最常见的约束条件有: (1)时间窗口约束.车辆必须在规定的时间窗 口内服务装货点或卸货点.如果车辆在时刻a、之前 到达点1，必须在点i等待到a，才能开始装卸货.车 辆在时刻b、之后到达点i，则无法按时完成该点的 装卸货任务，因而必须加以惩罚. (2)访问约束.车辆到客户的装货点装货，然后 运输到客户指定的卸货点卸货.每一个点都必须被 服务且只能被服务一次. (3)车库约束.车辆必须从车库出发到某一装 货点，最后从某一卸货点返回车库. (4)次序约束.客户的装货点必须在对应的卸 货点之前被访问. (5)容量约束.任何时刻车辆所载货物量不能 超过车辆的最大负荷，即每个客户的需求量不能超 过车辆的最大负荷. (6)独占约束.车辆在客户的装货点装货之后 必须立即运输到该客户的卸货点卸货. E-PDPTW问题的优化目标是在满足上述约束 的情况下，寻找车辆从车库出发服务所有客户并最 终返回车库的最优运输路径，使总运输代价最小. 1.2 E-PDPTW问题的性质 设8;是车辆服务的第i个客户(8。和8n+1表示 车库)，则车辆服务的所有客户的顺序组成了车辆路 径 r=份0 , 81, *-*, Un, 8n+1 ).图 1显示了单车 E-PDPTW的一个典型路径的情况.图中注明了装 货点和卸货点的对应关系，实线表示车辆在装货点 和卸货点之间的运行路程，虚线则是车辆空车运行 的路程. 1.2.1 目标函数的简化 设路径r的目标函数为 卸货点 装货点 图1 E-PDPT W问题的典型路径 Fig. 1 The typical route of E-PDPTW f (r)一名‘。。+艺CD, P, 其中:CP,.D,为车辆服务第i个客户8、的代价，即从 客户8、的装货点尸:运货到其卸货点D:的代价; CD,` PBi+ 1为车辆从第i个客户8;的卸货点D。到第 i十1个客户Si+，的装货点pa =+，的空车运行代价(第 0个客户和第n十1客户为车库).假设车辆服务客 户的单位代价和空车运行的单位代价都是固定的， 那么代价CP,.DS.对于问题的所有可行解都是不变的， 称为车辆的固定代价，它不会影响目标函数，因而可 以被忽略. 性质1 E-PDPTW问题的目标函数仅仅决定 于车辆的空车运行代价，而与车辆固定代价无关. 1.2.2 客户装货点和却货点的合并 E-PDPTW 问题中，因为客户对为其服务的车辆具有独占性，车 辆在客户的装货点装货后必须立即赶到相应的卸货 点卸货，然后才能继续服务别的客户.因此，每个客 户i的装货地点P‘和卸货地点D，可以当作一个点 PD来处理. 性质2 E-PDPTW问题中，每个客户的装货 点P和相应的卸货点D可以看成一个点PD.两个 PD点之间的代价就是从第1个点的卸货点到第2 个点的装货点的空车运行代价. 1.2.3 时间窗v的简化 尸D点的时间窗口由装 货点时间窗口〔ap,b,〕、卸货点时间窗口[aD,b司以 及从装货点到卸货点的车辆运行时间tpD 3个要素 确定.设「ao,b月为[aD,b习减去tPD后的时间窗口. 图2给出了时间窗口[ap,bp〕和〔a乞,b乞〕的全部6种 可能的情况.其中阴影部分表示点PD的时间窗口 CaPD,bPD1，车辆只要在该时间窗口内访问客户的装 货点，就一定可以在其卸货点的时间窗口内到达卸 货点，从而满足时间窗口约束. 对于图2中时间窗口「ap,bp〕与巨乞,b幻无公共 区间的两种情况:① 图2表示车辆在装货点的时 间窗口内装货后，无论如何也不能在卸货点的时间 窗口内卸货.这种情况是没有可行解的，在实际问题 中不应该出现;② 图2 (c)表示车辆在装货点的时间 窗口内装货后，必须在装货点或卸货点等待一段时 万方数据 第 3期 贾永基，等:单车独占性带时间窗口装却货问题的分析与算法 间才能在卸货点的时间窗口内卸货.因此车辆只有 在时刻bP到达装货点装货时，运输代价才最小.在 这种情况下，车辆的等待时间乙=aD-b'p是车辆的 固定代价，在问题所有的可行解中都是不变的，因此 乙可以合并到客户的服务时间中去. ap- bp ap by ap by (d) ab臀 bD ap崖夔Op M ???????? ? ????? ?? ? ? ? ?? ? ? ? ? ? ? ? ? 、 ?? ? ? ? ? ?? ? ? ?? ，? ? ? ? ? ? ?? ? ? ?? 图2 PD点的时间窗口 Fig. 2 Time window of PD node 性质3 E-PDPTW 问题中，对任意一个PD; 点的时间窗口[aPD. f bPD,〕可以表示如下:若bp.镇 aDi _ tP'D;，则aPD一bPD。一bp.;否则，aPD、一max { a p,, aDi一tPI.D}9bPD.=min { bp.， , bD.一tPiDi}· 1.2.4 距离不对称性 由于PD点由装货点尸和 卸货点D所构成，因此任意两个PD点之间的距离 具有不对称性，如图3所示. 图3 PD点之间的距离不对称性 Fig. 3 Distance asymmetry between PD nodes (1)利用最远插人算法[151得到单车E-PDPTW 问题的初始解; (2)依次执行步骤:① 使用3-opt优化算法改 进得到的解，②使用删除重插人优化算法进一步改 进解，直到解未得到改进的次数达到h. 2.1 最远插入算法 本文利用最远插人算法[Cs1来构造单车 E-PDPT W问题的初始可行解，其不同于Solomon 的一般插人算法[Cs1之处在于不是随机选择要插人的 客户，而是选择离车库最远的客户优先插人，以得到 比较好的初始解.由于前面i - 1个客户已经插人到 路径中去，对于待插人的第i个客户，需要考虑的插 入位置有i个.因此最远插人算法的时间复杂度为 O(n2). 2. 2 3-opt优化算法 3-opt优化算法为: (1)从路径中删除3条边，从路径别的部分加 上3条边，使得路径保持完整.如果交换使得路径可 行且运输代价减少，则保留交换结果;否则，不保留 交换结果. (2)重复步骤(1)，直到尝试了所有可能交换不 能改进解为止. 设 3-opt优化算法中，交换的边是(i,i+l), (j,j+l)和((k,k+l)，有图4所示的4种交换情况. 图4(b),(c),(d) 3种情况类似，路径(i+l,...,j)和 (j+1, """,k)至少有一个被反向，而在图4(a)中，路 径((i+1,..., j)和((j+1,""",k)的方向和原路径一 致.对于E-PDPTW 问题来说，由于时间窗口的存 在，路径的反向会导致大量的不可行解的出现，从而 极大地增加计算时间.因此，本文选择图4(a)作为 3-opt优化算法的交换结果.其时间复杂度为 O(n3). 性质4 E-PDPTW 问题中，任意两点PD，和 PD，之间的距离具有不对称性，即 d PDT PDT一d DT .， # dPD.PD.一dDiPi 1.2.5 E-PDPTW 问题的重新描述 E-PDPTW 问题可看作不对称距离带时间窗口旅行商问题:车 辆从车库出发，服务n个客户PD;(i=1,2，二。,n), 然后返回车库，每一个客户PD，必须在时间窗口 CaPD. , bPD. I内被服务且只能被服务一次. 2 求解单车E-PDPTW 问题的两阶 段快速算法 单车E-PDPTW问题的两阶段快速算法为: 不二万并几二k'". 、、一_____，一碑 、‘，，____户碑尸户 (b) 卜+祥 =mss=

书

关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf

子 ->i+ 、-一______--户- 图4 3-opt算法示意图 Fig. 4 Illustration of 3-opt algorithm 万方数据 上 海 交 通 大 学 学 报 第 39卷 2.3 删除重插入优化算法 时间代价的权值为0.1.所有结果都是运行10次所 删除重插人优化算法是从路径中删除一个客 取的平均值.测试结果表明，本文提出的两阶段快速 户，并立即把该客户插人到原路径来改进解的一种 算法是求解E-PDPTW 问题的一种有效、快速算 简单优化方法.客户重插入到原路径后，即使不能改 法. 进路径，但也不会得到比原路径更差的结果.设L 是车辆路径中所有客户的集合. 删除重插人优化算法为: (1)如果集合L中的所有客户都已经被选择， 停止;否则，依次选择L中的每一个客户， (2)从路径中删除被选择的客户，然后找到该 客户重新插入到原路径的最优插入位置，使代价的 增加最小，并完成插人，转步骤(1). 很显然，删除重插人优化算法的时间复杂度为 O W ). 2.4 两阶段快速算法复杂度分析 由上述分析可知，最远插人算法、3-opt交换算 法和删除重插人优化算法的时间复杂度分别为 OW) ,0(n3)和O (n2)，因此，两阶段快速算法的时 间复杂度就是O(hn3).一般来说，h是一个不大的 数，因此求解单车E-PDPTW问题的两阶段快速算 法的时间复杂度是O(n3). 4 结 语 本文给出了E-PDPT W 问题的数学描述，分析 了该问题的4个性质，并把问题简化为不对称带时 间窗口TSP问题，提出了求解单车E-PDPTW问题 的两阶段快速算法，该算法的时间复杂度只有 O (n3)，远远小于一般PDPT W问题的各种求解算 法.测试结果验证了本文算法的有效性和快速性. 参考文献: [1] [2〕 3 测试结果 为了保证测试结果具有实际意义，使用随机化 方法生成具有实际问题特征的测试数据.程序是用 C}十语言编写的，在P4 1. 6GB,128MB内存的机器 上测试，测试结果如表1所示. 表1 不同客户规模的运行结果 Tab. 1 The test results of different customer scale [3] [4] 客户总数 初始解代价 最终解代价 运行时间/ms ? ? ? ? ? ? ?? ?? ? ﹂ ? ? ? ?? ，? ?? ?? ， ? ?? ? ? ? ? ? ? ?? ??????????? ? ? ? ?? ?? ????????????????? ? ?? ??????????????????????????????? 1 212 2 565 7 904 38 647 214 918 756 1 065 3 213 12 646 91 704 400 026 [5] ?? ?? ? ? ?? ? ? ?? ?? ? ? ? ???????????， ? ? ? ? ﹂ 1 000 950 579 表1中，客户总数从小规模的20个客户直到大 规模的1 000个客户.初始解和最终解代价都是车 [6] 辆行驶距离和客户等待时间的加权和.在本文测试 中选择车辆行驶距离代价的权值为1，而客户等待 贾永基，谷寒雨，席裕庚.求解PDPTW问题的一种快 速禁忌搜索算法仁J1.控制与决策，2004,19(l):57- 60. JIA Yong-ji，GU Han-yu，XI Yu-geng. Quick taboo search algorithm for solving PDPTW problem仁J ]. Control and Decision, 2004,19 (1):57一60. William P, Nanry J, Barnes W. Solving the pickup and delivery problem with time windows using reac- tive tabu search[J]. Transportation Research Part B, 2000,34(1):107一121. Lau H C, Liang Z. Pickup and delivery with time win- dows:algorithms and test case generation[A〕. Proceedings of the 13th IEEE International Confer- ence on Tools with Artificial Intelligence (ICTAI' 01) 民〕.Dallas, Texas，USA: IEEE Computer Society, 2001. 333一340. LiH, Lim A. A metaheuristic for the pickup and de- livery problem with time windows仁A]. Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence(ICTAI' 01)[C〕.Dallas， Texas，USA: IEEE Computer Society, 2001. 160一 167. Renaud J，Boctor F F, Ouenniche J. A heuristic for the pickup and delivery traveling salesman problem [j]. Computers&Operations Research, 2000,27(3): 905一 916. Solomon M. Algorithms for the vehicle routing and scheduling problems with time window constraints 仁J]. Operations Research, 1987,35(2):254一265. 万方数据