租赁车辆运输外包模式下多车场周期车辆路径问题
张军，唐加福，潘震东
（东北大学教育部流程工业综合自动化重点实验室，沈阳 110004）
摘要：多车场周期车辆路径问题是车辆路径问题的推广。随着对车辆路径问题研究的深入，根据实际问题所抽象出的模型不再是仅由单车场单周期车辆路径问题模型描述，多车场周期车辆路径问题的研究则显得更加贴近实际。本文提出了一种在租赁车辆运输外包模式下，多个车场周期车辆路径问题的模型，该模型不同于一般的多车场周期车辆路径问题模型，其将周期内租赁的车辆数作为决策变量进行建模，最小化周期内运输的总费用。
关键词：租赁车辆运输外包；多车场；周期车辆路径问题
0引言
商品配送是供应链管理中的一个重要环节，如何安排车辆行驶路线使得商品配送过程合理化即车辆路径问题（Vehicle Routing Problem, VRP），对于整个物流运输成本及效益影响至关重要。VRP自1959年首次被提出后就引起了优化领域的普遍关注[1-4]，对该问题的研究也取得了空前丰富的成果。根据约束条件的不同，VRP问题已经衍生出多种变形，如Stochastic VRP(SVRP), Split Delivery VRP(SDVRP), Multiple Depot VRP(MDVRP), VRP with Time Windows(VRPTW)等，这些VRP问题模型中除MDVRP之外，其他VRP问题通常只考虑存在一个车场的情况下，且周期均为单周期。
在实际商品分销过程中，由于服务的客户点分散在不同区域，分销由多个分销中心来完成，MDVRP是VRP问题的一个合理扩展。对货物的实际配送一般也在一个给定的计划期内完成，这是由于客户对商品的需求不会以天为单位被满足，车辆路径在给定计划期内被安排，在该给定计划期内以一定访问频率满足客户每天的需求。因此将车辆路径问题扩展到多车场周期车辆路径问题(Multi-Depot Periodic Vehicle Routing Problem, MDPVRP)更加符合实际需要。尽管与一般的VRP相比MDPVRP解决实际问题的能力显著增强，但是关于该方面的文献非常缺乏。MDPVRP同时决策了每天需要访问的客户和周期内每天的车辆路径安排，最小化总的运输费用。Mingozzi[5] 提出了一个整数规划模型描述MDPVRP，该模型是对有能力限制的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)集划分模型[6]的扩展。Parthanadee [7]采用混合整数规划模型描述了多产品，多车场周期分销问题。MDPVRP问题是将MDVRP与周期车辆路径问题(Periodic VRP, PVRP)[8]需要解决的客户与车场的分配和客户与其被访问的时间组合的分配同时考虑下的车辆路径问题，是对MDVRP、PVRP问题的推广。关于MDVRP和PVRP方面的文献相对比较有限，对MDVRP与PVRP两类问题的研究则通常分为两类，一类将研究重点放在求解算法的设计上，有效的启发式算法被相继提出[9,10]；另一类将研究重点放在增加不同的约束对模型进行扩展。Cordeau[11]，Tansini[12]在MDVRP模型中加入时间窗约束；Lim[13]研究了固定车辆数目的多车场车辆路径问题；Dondo [14]考虑了采用不同种类的车辆运输情况下的多车场车辆路径问题；Crevier[15]提出了车辆行驶途中可以通过中间车场进行补充货物的多车场车辆路径问题。PVRP将VRP问题从单周期推广到多周期，现实生活中其具有许多实际的应用[16-19]，如食品行业的分销，汽车行业的零部件配送，垃圾收集，自动贩卖机中商品配送等等。对其模型的变形相对较少，Francis[20]提出将客户的服务频率作为决策变量的PVRP问题模型；Angelelli[21]研究通过中间工厂补充车辆能力对PVRP模型进行扩展。
租赁车辆运输外包模式下多车场周期车辆路径问题(Multi-depot periodic vehicle routing problem with vehicle rent way, MDPVRP-VH)是在MDPVRP的基础上提出出来，是对MDPVRP问题的扩展，其不同于一般的MDPVRP问题在于周期内租用的车辆数作为决策变量[22]。由于目前的研究中通常假定运输能力是无限的或者是一个常数，仅作为能力约束存在，目标函数中车辆的费用被忽略不计。固定的车辆数目使得企业不能灵活地应对市场需求，造成成本浪费或不足。有鉴于此及MDPVRP目前的研究进展，提出了租赁车辆运输外包模式下多车场周期车辆路径问题模型。
问题描述与假设
租赁车辆运输外包模式下多车场周期车辆路径问题以一个分销企业为背景，假设在一个分销网络中，M个分销中心即车场为地理上分散分布的N个零售商即客户点提供一种产品，每个分销中心都具有足够的供应能力。整个计划期被分解为多个时间单位，时间单位的长度为天，整个计划期的长度为T天。该网络可以采用多图G＝（V,A）进行描述，其中顶点集 V 包括Vc 和 Vd 两个集合，Vc={v1, v2, ……vN}表示客户点集；Vd={vN+1, vN+2, ……vN+M} 表示车场集合；弧集合 A={(vi , vj) k,l }，其中k和 l (1≤l≤T)分别指访问车辆和被访问的日期，假设每个车场拥有足够的车辆数目K。每一条弧(vi , vj) k,l对应于一个非负的费用, 该费用与第l天被第k辆车访问的客户点i到客户点j之间的距离成比例，距离矩阵D = (Dij)为边(vi, vj)的长度，假设D对称，并且任意三点之间的距离满足三角不等式，任意两点之间的距离不受车辆及运送时间的影响，只与两点间距离有关。所有的运输车辆具有相同的型号，且其载重量为Q，每辆车每天只能完成一条路径的访问，并且该车辆起始于同一车场。在整个计划期内，每个客户点i被访问的频率为ei，每个客户点预先给定的访问时间组合为Ci。假设一个客户点的访问频率ei＝2，计划期长度为7天，Ci＝{{1, 6}, {2, 4}, {3, 7}}, 那么客户点只能在星期一和星期六；星期二和星期四；或者星期三和星期日，这三组组合中选取一个组合中指定的日期进行访问。每个客户点i在一个给定的访问时间间隔都具有一个已知的需求量qi(0≤qi≤Q)，并且该需求必须被一辆车仅访问一次来满足。
MDPVRP-VH在整个计划期内，采用租赁车辆运输外包的方式进行运输。采用该方式的企业将其运输业务以租赁车辆的方式转让给专业的运输企业，通过计划期内从专业运输企业（Professional Transportation Enterprise, PTE）租赁固定数目的车辆来管理运输业务。该运输外包模式的特点是[22]：1）企业在一个计划期内租赁的车辆数不再是已知的常数，而是一个决策变量，需要根据计划期内的需求量和运输计划确定，因此运输能力是柔性的，能更好地面对不断变化的市场需求；2）企业制定运输计划，运输公司只负责执行具体的运输安排；3）企业在计划期内按照合同租用运输公司的车辆，除正常的运输成本外，需要根据租用的车辆数一次性支付租金；4）运输公司在租用计划期内确保每个阶段企业需要的车辆能力（数）；此外，运输公司可以根据企业每个阶段需要的车辆能力（可能有剩余能力）制订自己的运输能力分配计划，以充分利用车辆能力和平衡总的运输能力。
MDPVRP-VH中车辆运行路径需要满足一些VRP及MDVRP的约束：在每个时间单位里，1)从某个车场出发的每辆车，服务一些客户点后，必须回到出发车场；2) 每个客户点都必须仅被一辆车访问且只访问一次；3)每辆车的载重量不能超过该车的容量限制；4) 车辆不能从一个车场到另一个车场，且路径中不能出现回环。
MDPVRP-VH需要解决的问题是同时决策每个车场服务的客户点，每个客户点在整个计划期内被访问的时间组合及每个时间单位内车辆的行驶路径，而且要确定完成运输任务所要租赁车辆的最优数目，使得计划期内运输总费用最小。
模型建立
2．1符号
MDPVRP-VH的数学模型可以描述为0－1混合整数规划模型，模型中需要用到的符号定义如下：
1) 下标：
p=车场标号, p= 1, 2,…, M；
i,j=顶点标号，i,j∈V；
k=车辆标号，k= 1, 2,…,K；
l=在计划期T内运输可用的时段, t=1, 2,…,T；
r=客户访问组合中的标号，r∈C；
2) 参数：
Dij=点i和j之间的距离(公里), i,j∈V；
qi=客户点i在一个给定的访问时间间隔内的需求(吨) ,i= 1, 2,…,N；
Ci=客户点i在计划期内的访问组合；
(i=一台车发车到客户点i往返一次的固定费用(元/辆)，,i= 1, 2,…,N；
Cd=行驶单位距离的费用(元/公里)；
Cv=计划期内租赁单位车辆的固定费用(元/辆)；
K=每个车场所拥有的车辆数目(辆)；
Q=车辆的最大载重能力(吨)；
3) 决策变量：
Nt=在时段t可用来运输的车辆数目；
N= max{Nt}，计划期内需要租赁的车辆数；
2．2数学模型
在MDPVRP-VH中，目标函数的组成分为三部分，车辆的行驶费用即跟运输距离相关的费用；车辆的发车费用；在计划期内车辆的租赁费用。
与运距有关的费用正比于车辆的行驶距离，因此该费用可以表示为如（1）式所示：
(1)
车辆的固定发车费用即增加一辆车的边际费用，一般认为派出一辆车的固定费用远远高于车辆的行驶费用。将发车费用考虑到目标函数中可以减少车辆的使用，进而减少总的运输费用。该部分费用与车辆使用数目成正比，则发车费用为：
(2)
在计划期内车辆的租赁费用为整个计划期内每个时间单位使用车辆数目的最大值，这样才能满足整个计划期内每个时间单位的车辆需求，该部分费用如下：
(3)
因此MDPVRP-VH的数学模型其目标函数可以描述如下：
(4)
其约束条件如下：
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
其中(5)式表示对于任何一个客户点，必须选择其访问时间组合中的一个；(6)式保证每个客户点只是在选择的访问时间组合中的时间段被访问；约束(7)保证每个客户点在每个单位时间段内只能被一辆车访问一次；(8)式确保任何车场的任一从该车场出发的车辆，服务结束后当天返回该车场，同时保证当天每辆车只被使用一次；(9)式使得任何两个车场之间不存在路径；(10)式是标准的排除子环约束；约束(11)是车辆的容量限制；(12)式表示在一个计划期内，需要租赁的车辆数目；(13)-(16)式为决策变量的取值约束。
结论
本文以生产分销企业为背景，将一般的MDPVRP问题模型与租赁车辆运输外包这种运输模式相结合，提出了一种采用租赁车辆运输外包运输模式的MDPVRP模型。在一般的MDPVRP模型中，运输方式通常不被考虑，而将重点放在路径的规划和访问时间组合的分配上，但是在实际的物流运作中，运输方式的选择必然会影响到路径的制定，因此提出的模型相比一般的MDPVRP问题更贴近于对实际问题的建模。
参考文献：
[1] Dror M, Trudeau P. Stochastic vehicle routing with modified savings algorithm [J]. European Journal of Operational Research, 1986, 23(2):228-235.
[2] Dror M, Laporte G, Trudeau P. Vehicle routing with split deliveries [J]. Discrete Applied Mathematics, 1994, 50(3): 239-254.
[3] Renaud J, Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle routing problem [J].Computers & Operations Research, 1996, 23(3): 229-235.
[4] Russell R A. Hybrid heuristics for the vehicle routing problem with time windows [J]. Transportation Science, 1995, 29(2): 156–166.
[5] Mingozzi A. The multi-depot periodic vehicle routing problem [J]. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2005, 3607: 347-350.
[6] Fukasawa R, Lysgaard J, de Aragao M P, et al. Robust branch-and-cut-and-price for the capacitated vehicle routing problem [C]. Integer Programming and Combinatorial Optimization 10th International IPCO Conference. Lecture Notes in Computer Science, 3064, Springer-Verlag, Berlin, -15.
[7] Parthanadee P, Logendran R. Periodic product distribution from multi-depots under limited supplies [J]. IIE Transactions (Institute of Industrial Engineers), 2006, 38 (11):1009-1026.
[8] Tan C C R, Beasley J E. A heuristic algorithm for the period vehicle routing problem [J]. Omega, 1984, 12(5): 497-504.
[9] Pisinger D, Ropke S. A general heuristic for vehicle routing problems [J]. Computers & Operations Research, 2007, 34(8):2403-2435.
[10] Cordeau J F, Gendreau M, Laporte G. A tabu search heuristic for periodic and multi-depot vehicle routing problems [J]. Networks, 1997, 30(2):105-119.
[11] Cordeau J F, Laporte G, Mercier A. Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows[J]. Journal of the Operational Research Society, 2004, 55(5): 542-546.
[12] Tansini L, Viera O. New measures of proximity for the assignment algorithms in the MDVRPTW [J]. Journal of the Operational Research Society, 2006, 57(3):241-249.
[13] Lim A, Zhu W. A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach[C]. Advances in Applied Artificial International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006. Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 4031 LNAI, Springer-Verlag, Berlin, 2006. 282-291.
[14] Dondo R, Cerdá J. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows [J].European Journal of Operational Research, 2007, 176(3): 1478-1507.
[15] Crevier B, Cordeau J F, Laporte G. The multi-depot vehicle routing problem with inter-depot routes [J]. European Journal of Operational Research, 2007, 176(2):756-773.
[16] Carter M W, Farolden J M, Laporte G, et al. Solving an integrated logistics problem arising in grocery distribution[J]. INFOR, 1996, 34(4): 290-306.
[17] Alegre J, Laguna M, Pacheco J, Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts [J]. European Journal of Operational Research, 2007, 179(3):736-746.
[18] Beltrami E J, Bodin L D. Networks and vehicle routing for municipal waste collection [J]. Networks, 1974, 4(1): 65–94.
[19] Campbell A M, Hardin J R. Vehicle minimization for periodic deliveries [J]. European Journal of Operational Research, 2005, 165(3):668-84.
[20] Francis P, Smilowitz K. The Period Vehicle Routing Problem with Service Choice [J]. Transportation Science,2006, 40(4):439–454.
[21] Angelelli E, Speranza M G. The periodic vehicle routing problem with intermediate facilities [J]. European Journal of Operational Research,2002, 137(2), 233–247.
[22] Tang J F, Yung K L, Liu S X. Lagrange Relaxation Decomposition for Synchronized Production and Transportation Planning with Flexible Vehicles[C]. 2005 International Conference on Service Systems and Service Management, IEEE, Piscataway, -361.
The multi-depot periodic vehicle routing problem with vehicle rent way
ZHANG Jun, TANG Jia-fu, PAN Zhen-dong
Key Laboratory of Integrated Automation of Process Industry of MOE, Northeastern University, Shenyang, 110004, China
Abstract: The Multi-depot Periodic Vehicle Routing Problem (MDPVRP) is the generalization of Vehicle Routing Problem. With researching the Vehicle Routing Problem in depth, the model abstracted from the practical problem is not described by single-depot and single-period model. The research on multi-depot periodic vehicle routing problem is more practical. This paper proposes a model of multi-depot periodic vehicle routing problem with vehicle rent way. This model is different from the general MDPVRP. The amount of vehicles rent in the planning period is viewed upon as an operational decision variant to model the problem. The objective is to minimize the total transportation cost in the planning period.
Key words: vehicle rent way; multi-depot; periodic vehicle routing problem
