摘要：无车承运人平台为整合短途运输车辆实现长途运输任务提供有力条件，本文针对此情形，研究了考虑车辆回程折扣、商品到达时间和商品中转换装时间同步性的分段分包运输网络设计。首先为该问题建立基于节点-弧模型，然后为了求解更大规模的问题，将该模型转化为基于商品路径的集合模型，并根据该模型开发了相应的近似算法。最后，数据实验表明该近似算法在求解大规模算例时，求解质量和运行时间均优于软件CPLEX基于节点-弧模型的结果。

　　关键词：分段分包;时间同步;路径集合模型;近似算法

　　1.引言

　　无车承运人凭借信息平台和站点资源，通过契约与当地运输公司或个体合作组织长途运输，该组织模式下同一长途运输任务将由多运输主体接力完成，改变了传统单一主体实施的局面。但由于多主体参与运输，同一运输任务由多辆车协同完成，车辆间的协调变得复杂，如何优化商品路径及车辆协调成为无车承运人面临的重要问题。为此，研究了分段分包的运输网络设计问题(Subsection and Subcontracting Transit Network Design Problem，SSTNDP)。SSTNDP问题考虑了商品的时间窗和商品在转运站点的同步以及车辆的回程折扣和车辆资源的有限性，目前，对于SSTNDP问题研究的文献很少，但有文献对服务网络设计问题(Service Network Design Problem，SNDP)进行了研究。

　　Ghamlouche et al.(2004)[1]建立了弧变量模型，使用的是两点之间的流量限制，然而，考虑到实际的运输问题，车辆容量限制更普遍一些。所以，文中的容量限制指的是单辆车的载重量限制。在模型上，既建立了弧变量模型，也建立了路线变量模型。在成本上，考虑了整车租赁成本和单位商品流的装卸成本，且整车租赁成本和两点之间的运输距离密切相关，可以反映距离对成本产生的影响。在车型上，考虑了多种车型、车辆容量、车辆租赁成本等因素，而且允许多辆车服务一条弧线。Andersen et al.(2009a)[2]虽然考虑了多车型问题，但是假设车辆资源充足。但是，在实际运输中，车辆资源是有限的，需要合理调度有限的资源完成运输。Wang et al.(2019)[3]考虑了车辆资源的有限性，但是忽略了车辆之间的协同。因此，文中考虑了整车租赁成本、多车型、车辆资源有限性以及车辆之间的协同问题。与弧线设计平衡和资产设计平衡不同，SSTNDP问题考虑的是从无车承运人平台租赁车辆，车辆完成运输任务后，如果没有返程商品需要运输，就会立即释放，不必回到出发点，因此，强调的是资产设计不平衡问题。Medina et al.(2018)[4]研究了整合长途和短途运输的服务网络设计问题，货物需要从起点运到整合网络的起点，从整合网络的起点运到整合网络的终点，从整合网络的终点运到顾客手中，通过时间窗约束确保整合网络起点和终点的同步性问题。但是，这里的时间不是变量，而是给定的一个时间集合。SSTNDP问题充分考虑了商品在运输网络中的时间因素，包括商品的最早出发时间、最晚到达时间，运输时间，以及商品和商品之间、商品和车辆之间在各个节点的时间同步性要求，将时间作为未知变量，计算出商品和车辆在站点的准确时间，为商品流分布、车辆部署提供准确的时间计划表，对于商品整合、提高运输时效性具有重要作用。

　　2.问题描述及模型建立

　　2.1 问题描述

　　在SSTNDP问题中，有若干站点，各个站点有一定数量的车辆，且车辆是不同车型的，不同车型的车辆的载重量和单位距离租赁成本不同。现有商品需要从一个站点(起点)，运送到另一个站点(终点)，商品从各自起点出发选择网络中开通的弧线形成一条从起点到终点的连续运输路线，被运输到对应的终点，这里，不同的商品是指起点不同或者终点不同的货物。每个弧线上分布的商品流作为一段独立运输任务，各段根据商品流的分布租赁一定数量和型号的车辆完成运输。租赁成本和车型以及站点之间的距离有关，如果反向弧线也有商品分布，则车辆回程费用有折扣优惠。商品在起点会发生装货成本，在终点会发生卸货成本，在中转站点会发生装卸成本，装卸成本和商品的运量有关。这样就可以利用回程车辆完成商品的运输，减少整车租赁成本，及降低车辆空程率。网络中的站点除了是商品的起点和终点外，也可能是商品的中转站点，不同商品在中转站点整合换装时，不同车辆之间需要满足时间同步性要求。网络中各段运输任务租赁服务车辆时会发生整车租赁成本。

　　SSTNDP问题考虑了多车型、有限的车辆资源、车辆回程折扣、商品最晚到达时间以及车辆之间的时间同步性等约束，以整车租赁成本和装卸成本最小化为目标函数，建立了基于节点-弧的混合整数规划模型[5]。

　　2.2 基于商品路径集合的模型

　　由于基于节点-弧的混合整数规划模型中，弧为主要决策变量，变量取值范围很大，为了减少变量取值范围，降低问题的复杂度，将基于节点-弧的混合整数规划模型转化为基于商品路径集合的模型，以商品的路径为主要决策变量。通过控制商品路径集合的规模控制求解的复杂度。下面将基于节点-弧的混合整数规划模型转化为基于商品路径集合的模型。

　　2.2.1 参数及变量

　　参数：

　　N：节点集合;A：弧线集合，(i，j)∈A，i∈A，i∈N;j∈N

　　P：商品集合，p∈P;dp：商品p的终点;setp：商品P的候选路线集合;

　　V：车辆集合，v∈V;ov：车辆v的起点;

　　parcijpr：表示商品p的第r条路线是否经过有向弧(i，j)，经过为1，不经过为0;

　　pcostrp：商品p的第r条路线的成本，pcostrp=■(α+β)θrparcijpr。

　　变量：

　　θrp：商品p的第r条路线，θrp≥0;yijv：车辆v服务弧线(i，j)，yijv≥0;

　　zijpv：商品p由服务弧线(i，j)的车辆v来运输，zijpv≥0;

　　dPip：商品p离开节点i的时间，dPip≥0;dPjp：商品p到达节点的时间，dPjp≥0;

　　dvijv：车辆v从节点i离开，前往节点j的时间，dvijv≥0;

　　avjiv：车辆v从节点j出发，到达节点i的时间，avijv≥0。

　　2.2.2 数学模型

　　目标函数：

　　minimizeRMP_cost=■■(coiv(yoiv+(1+ωv)yoiv))+■■pcostrpθrp (1)

　　目标函数(1)是最小化车辆租赁成本和商品路径装卸成本之和。

　　约束条件：

　　a. 商品路径约束

　　■θrp=1 ?坌p∈P (2)

　　约束(2)表示每个商品至少要有一条运输路线将商品从起点运输到对应的终点。

　　b. 车辆约束

　　■yoiv≤1 ?坌v∈V：o=ov (3)

　　yiov≤yoiv ?坌v∈V：o=ov ?坌i∈N (4)

　　■yoiv=0 ?坌v∈V：o=ov ?坌i∈N：i≠0 (5)

　　■θrpparcijpr≤■yijv ?坌p∈P，?坌i∈N，?坌j∈N (6)

　　■zijpvqp≤yijvQv ?坌v∈V，?坌i∈N，?坌j∈N (7)

　　■zijpv=■θrpparcijpr ?坌p∈P，?坌i∈N，?坌j∈N (8)

　　■ ■yijv≤νi ?坌i∈N (9)

　　约束(3)表示每辆车至多被使用一次;约束(4)表示车辆有去程才有回程;约束(5)表示车辆只服务自己所在的干线;约束(6)表示如果有商品分布在弧线上，则必然有车辆为该弧线提供服务;约束(7)表示服务某一弧线的车辆所装载的商品量不能超过该车辆的固定载重量。约束(8)表示如果有商品分布在弧线上，该商品一定由服务该弧线的某一辆车来完成运输。约束(9)表示每个车场使用的车辆数量不得超过车场的可得车辆数量。

　　c. 时间约束

　　apjp≥dpip+tij-M(1-θrpparcijpr)?坌p∈P，?坌r∈setp，?坌i∈N，?坌j∈N (10)

　　apjp≤dpip+tij+M(1-θrpparcijpr)?坌p∈P，?坌r∈setp，?坌i∈N，?坌j∈N(11)

　　apdp-etp≥-M(1-θrpparcidpr) ?坌p∈P：d∈dp，?坌r∈setp，?坌i∈N：i≠d (12)

　　apdp-ltp≤-M(1-θrpparcidpr) ?坌p∈P：d∈dp，?坌r∈setp，?坌i∈N：i≠d (13)

　　dpip≥apip+sti ?坌p∈P，?坌i∈N (14)

　　apip-avjiv≤M(2-yjiv-θrpparcijpr)?坌p∈P，?坌r∈setp，?坌v∈V，?坌i∈N，?坌j∈N (15)

　　avjiv-apip≤M(2-yjiv-θrpparcijpr)?坌p∈P，?坌r∈setp，?坌v∈V，?坌i∈N，?坌j∈N (16)dpip-dvjiv≤M(2-yjiv-θrpparcijpr)?坌p∈P，?坌r∈setp，?坌v∈V，?坌i∈N，?坌j∈N (17)

　　dvjiv-dpip≤M(2-yjiv-θrpparcijpr)?坌p∈P，?坌r∈setp，?坌v∈V，?坌i∈N，?坌j∈N (18)

　　avoiv-dviov+sti≤M(2-yoiv-yiov) ?坌v∈V，o∈ov，?坌i∈N (19)

　　约束(10)和约束(11)表示有向弧线(i，J)上商品的到达时间等于离开时间加上运输时间;约束(12)和约束(13)表示商品要在指定的时间窗内到达终点;约束(14)表示商品离开某一节点的时间大于其到达该点的时间加上服务时间;约束(15)和约束(16)表示商品的到达时间和车辆的到达时间同步;约束(17)和约束(18)表示商品的离开时间和车辆的离开时间同步;约束(19)表示车辆回程离开时间大于该车辆去程到达时间加上服务时间。

　　3.近似算法设计及效率分析

　　3.1算法设计

　　将基于节点-弧的混合整数规划模型转化为基于商品路径集合的模型后，需要为商品寻找从起点运送到终点的完整路线，即为商品构造候选路线邻域。每种商品候选路线要满足商品最晚到达时间要求。商品候选路线邻域的构造思路是：对于某一商品，通过在该商品的起点和终点之间插入节点，以及将起点到该节点和该节点到终点两端的路线重组的方式构造新的路线;如果该商品候选路线数量小于等于指定路线数量，将该路线放入商品的候选路线中;如果该商品候选路线数量大于指定路线数量，删除已有候选路线中所耗时间最长的路线;最后，去掉不满足商品时间窗的路线，剩下的路线就是各个商品的候选路线。确定商品路径集合后，再调用CPLEX求解整个模型。

　　3.2 算例生成

　　SSTNDP问题所需要算例的信息应包括坐标点、坐标点服务时间、开通弧、商品起终点和需求量、商品最早达到时间和最晚到达时间、车辆类型、载重量和数量的信息。本部分根据Solomon算例[6]和Crainic et al.(2011)[7]使用的算例构造SSTNDP问题的测试算例，共构造了五种规模的算例：(1)5个节点8个商品16条弧(5-8-16);(2)10个节点15个商品35条弧(10-15-35);(3)10个节点25个商品40条弧(10-25-40);(4)20个节点40个商品120条弧(20-40-120)。SSTNDP问题算例的坐标点来自于Solomon算例[6]，算例中开通的弧、商品起终点和需求量来自于Crainic et al.(2011)[7]使用的算例。其他参数根据算例的相关信息进行构造。商品最早到达设为0，商品最晚到达时间和商品从起点到达终点的最短路径有关，设为最短路径对应时间的5倍，商品在站点的处理时间设为0.2。每个站点的车辆类型有两种，载重量分别是200和400，每个站点的车辆数量在不同规模的算例中是不同的，算例中每个节点均有两种车辆类型，第一种规模的算例每种车辆类型均有一辆车，其他规模的算例每种车辆类型均有两辆车。

　　3.3 效率分析

　　通过对基于节点-弧和基于商品路径集合的模型的求解效率分析发现，在1~15个算例中，近似算法均取得了最优解，且平均运行时间只有CPLEX的1/2;在16~30这15个算例中，近似算法取得了12个最优解，平均gap只有0.08%，平均运行时间只有CPLEX的1/144;在31~45这15个算例中，使用CPLEX求得6个最优解，使用近似算法求得5个最优解，而且，近似算法中有6个算例取得了比CPLEX更优的解，15个算例平均gap降低了1.03%，平均运行时间只有CPLEX的1/288;在46~47个算例中，使用近似算法平均gap降低了46.77%，平均运行时间只有CPLEX的1/8。因此，不论是从求解质量还是运行时间上，近似算法相对于CPLEX都表现出了良好的性能，尤其是在求解大规模的算例上更凸显出了优势。

　　4.结论

　　针对网络货运的运作模式，考虑了车辆回程折扣、商品到达时间和商品中转换装时间同步性等实际因素，研究了分段分包的网络设计问题，首先建立了该问题的节点-弧路线模型，然后转化为基于商品路径集合模型，提高求解效率。数据实验表明，随着问题规模的增加，近似算法效率优势越显著。C

　　(作者单位：南京农业大学信息管理学院)

　　基金项目：国家重点研发计划项目(2018YFB1403100),教育部人文社科项目(19YJC630079)

　　参考文献

　　[1] Ghamlouche I, Crainic T G, Gendreau M. Path relinking, cycle-based neigh-bourhoods and capacitated multicommodity network design[J]. Annals of Operations Research, 2004, 131:109-133.

　　[2] Andersen J, Crainic T G, Christiansen M. Service network design with management and coordination of multiple fleets[J]. European Journal of Operation Research, 2009a, 193(2):377-389.

　　[3] Wang Z, Qi M. Service network design considering multiple types of services. Transportation Research Part E, 2019(126):1-14.

　　[4] Medina J, Hewitt M, Lehué dé F, et al. Integrating long-haul and local transportation planning: the Service Network Design and Routing Problem[J]. EURO Journal on Transportation and Logistics, 2018.

　　[5] 李婷婷. 基于“互联网+物流”的干线运输服务网络设计问题研究 [D]. 南京：南京农业大学，2018.

　　[6] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2):254-265.

　　[7] Crainic T G, Frangioni A, Gendron B. Bundle-based relaxation methods for multicommodity cpacitated fixed charge network design problems. Discrete Applied Mathematics, 2001, 112:73-79.