【www.shanpow.com--科学试题】
货车调度篇一:城际干线甩挂运输的公路牵引车调度问题及其求解
? 城际干线甩挂运输的公路牵引车调度问题及其求解
城际干线甩挂运输的公路牵引车调度问题及其求解 李红启1，常馨玉1，朱晓宁2，卢 越3 (1.北京航空航天大学 交通科学与工程学院，北京 100191；2.北京交通大学 交通运输学院，北京 100044； 3.北京华运交通咨询开发公司，北京 100038) 摘要： 针对城际干线甩挂运输过程所涉及的公路牵引车调度，以整车运输和“多对多”式运输需求为基本特征，兼顾驾驶员与牵引车连续工作时间的约束，并以货运吨公里CO2排放量为目标函数，提出了城际干线运输中的牵引车调度问题。构建了LTDP问题的整数规划模型, 设计了基于模拟退火的求解算法主流程，辅以可选用的、针对主流程运算结果的后处理操作，以进一步提升满意解。该算法被运用于山东省城际干线甩挂运输网络实践算例求解。运算结果表明：本文所构建的整数规划模型及其启发式求解方法是可行和有效的，干线甩挂运输模式具有良好的节能减排效果。 关键词： 运输经济；牵引车调度；模拟退火；甩挂运输；干线 0 引言 甩挂运输被广泛应用于道路运输领域，其本质上是一种基于道路货运车辆调度的货运运力资源配置模式[1]。经济发达国家在20世纪60年代就已盛行汽车列车甩挂运输，该运输组织形式被推广应用于城际干线运输、城市配送以及多式联运领域。国外甩挂运输所用的汽车列车组合方式多种多样，如：卡车拖挂全挂车、牵引车拖挂半挂车、牵引车拖挂半挂车与全挂车等。我国甩挂运输的发展相对滞后、且目前只允许企业使用牵引车拖挂半挂车开展甩挂运输。自2009年交通运输部等部委联合发布《关于促进甩挂运输发展的通知》以来，物流运输企业开展甩挂运输不仅在体制上面临的制约越来越少，而且可以获得多种扶持。 由于可用车型多样，国外甩挂运输模式广泛应用于城际干线运输和城市配送等领域。现阶段我国企业能够用于开展甩挂运输的车型特点决定了城际干线运输是甩挂运输模式的主要应用领域。城际干线运输以网络化、规模化特征成为体现甩挂运输技术经济优势的依托条件，且城际干线运输的货物交流量大、运距长，便于实现甩挂运输货源组织的规模化，这有利于发挥甩挂运输的整车运输优势。对于物流运输企业而言，在货源组织和车辆装备条件都得以保证时，干线甩挂运输组织工作的重点就是甩挂运输车辆调度。 企业在由传统卡车运输模式向甩挂运输模式转变过程中，需要将其面向单体卡车的调度方式转变为面向汽车列车的调度模式。同单体卡车相比，汽车列车的动力部分和载货部分可自由分离与结合，这就增加了甩挂运输车辆调度工作的复杂性。从调度作业对象看，甩挂运输车辆调度包括牵引车调度、载货半挂车调度、空半挂车调度和汽车列车调度等。企业实践中的甩挂运输车辆调度往往是综合化的调度问题，即上述车辆调度类型的组合形式。 本文定位于牵引车调度这一甩挂运输车辆调度工作中最为核心的问题，建立公路牵引车调度问题数学模型，设计求解算法，并开展牵引车调度问题实践算例的求解与分析。 1 既有研究概述 相对于卡车，汽车列车能够通过动力部分和载货部分的自由分离和结合开展甩挂运输，从而获得更高的车辆使用效率[2-3]。学术界普遍认为汽车列车的调度问题很复杂，是NP难题，部分学者认为传统车辆调度问题(Vehicle Routing Problem，VRP)只是汽车列车调度问题的一个特例[4]。迄今国内外学术界在该类问题方面的研究成果主要体现为3类(其基本特征对比见表1)： (1)对于卡车与全挂车组合而成的汽车列车调
表1 VRP,TTRP,RRVRP和TSRP的一般特征对比
Tab. 1 Comparison of characteristics of VRP,TTRP,
RRVRP and TSRP
对比项VRP问题TTRP问题RRVRP问题TSRP问题所用车辆单体卡车卡车+全挂车牵引车+半挂车牵引车+半挂车网络节点中心场站和客户点中心场站、卡车客户点和汽车列车客户点中心场站和客户点中心场站和半挂车集散点运输需求零担零担整车整车服务领域短途配送短途配送、小区域运输城市垃圾回收城际干线、小区域运输客户点间的货运需求无无无有路径长度无限制无限制有限制有限制
度问题，有关研究一般称其为TTRP问题(Truck and Trailer Routing Problem)。TTRP问题可叙述为：一些客户点既可以由汽车列车服务，也可以由单独的卡车服务，而有些客户点仅能由卡车提供货运服务；设定卡车和挂车数量已知、路径上客户点的运量满足车辆载运能力约束；求解目标是寻找成本最低的车辆路径集，路径是闭合的，每个客户点都只被提供1次货运服务。TTRP问题的研究成果以文献[4-5]等为代表。 (2)迄今学术界针对牵引车和半挂车组合的调度问题的研究工作主要体现为RRVRP问题(Rollon-rolloff Vehicle Routing Problem)。RRVRP问题源于城市垃圾运输活动，垃圾运输车将空车厢送到垃圾收集点，车厢装满垃圾后，由垃圾运输车将重车厢运到垃圾集中处理站进行卸车和后续处理。垃圾运输车的作业方式与牵引车加半挂车的汽车列车作业方式类似。该问题的研究成果以文献[6-7]等为代表。 (3)另一类针对牵引车和半挂车组合的优化运用问题被称为TSRP问题(Tractor and Semi-trailer Routing Problem)。迄今学术界针对TSRP问题的研究背景主要有两种：短途(配送)运输和中长途(干线)运输。TSRP问题的短途运输应用背景包括厂内运输、局部性运输，如：梁波[8]研究了以大型钢铁企业内部物资运输为背景的TSRP问题；范宁宁[9]建立了以集疏运运营成本最小化为目标的数学模型来研究烟大滚装甩挂牵引车调度问题；张磊磊[10]以LPG炼油厂为牵引车场站、将牵引车加半挂车的汽车列车应用于LPG运输。鉴于该类汽车列车从事运输活动的规模经济优势，TSRP问题的干线运输应用前景更被看好。城际干线运输网络的几乎所有节点间均可能存在货运需求，这种节点间的运输需求呈现为“多对多”的关系，与VRP问题的节点间运输需求“一对多”的关系[11]明显不同。H. Li等[12-13]在城际干线运输网络上界定出TSRP问题。 2 数学模型与算例设计 2.1 问题特点与数学模型 区别于既有研究工作所提出的TTRP问题和RRVRP问题，本文瞄准物流运输企业运用汽车列车进行甩挂运输过程中所面对的牵引车调度这一核心问题，提出城际干线运输中的牵引车调度问题(Line-haul Tractor Dispatching Problem，LTDP)。LTDP问题有以下基本特点： (1)整车运输 甩挂运输的基本优势来源于牵引车和半挂车之间可用很短时间进行分离和结合作业，这便于以整个半挂车及其所载货物作为装卸和中转单元，从而大大压缩牵引车在场站内因等待装卸作业所需的停留时间。LTDP问题可以以半挂车为运输作业单位。 (2)“多对多”问题 运输网络由节点V(包括1个中心场站v0和n个半挂车集散点vi(i=1,2,…,n))和边A(A={(i,j)|i≠j,i,j=0，1，2，…,n})组成。中心场站是指可以存放大量牵引车、规模较大、在运输网络中处于枢纽地位的场站；半挂车集散点是指需要货运服务并进行半挂车甩挂作业的节点，其运输需求和保有的半挂车数量均不同。 LTDP问题的运输需求与传统VRP问题的最大区别在于LTDP问题考虑了半挂车集散点之间的货运需求，使问题变为“多对多”特征，货运需求变为货物交流矩阵形式。不妨将货运需求分为3类：由中心场站v0发往半挂车集散点vi(vj)的货运量记为d=(r01,r02,…,r0n)， 由vi(vj)发往v0的货运量记为p=(r10,r20,…,rn0)， n个半挂车集散点两两之间的货物流量记为矩阵B，其中rij表示任意两个半挂车集散点间的货运需求，以半挂车为运输单位，则货物流量矩阵，货运需求可表示为矩阵形式：。 (3)驾驶员与牵引车连续工作时间 在甩挂运输模式中，牵引车的利用率是焦点，而牵引车连续工作时间与驾驶员工作时间之间联系密切。由于人体持续工作耐力、车辆行驶过程安全要求等因素，驾驶员的法定工作时间是有硬性要求的，如在美国，卡车驾驶员连续行车时间不能超过10 h，在充分休息8 h的条件下，可在岗15 h(包括用于等待货物装卸、车辆维修保养等的停留时间)[14]。牵引车连续工作时间极大影响着LTDP问题路径方案的路径长度。 (4)考虑甩挂运输节能减排效果的目标函数 甩挂运输竞争优势的发挥依赖于车辆装备和组织管理技术，在相应的市场条件和软硬件装备条件下，甩挂运输的技术经济特点得以发挥，由此带来的效果是道路货运效率的提升,这意味着以更少的投入获得更多的产出。道路货运的投入因素体现为固定成本投入和变动成本投入，其中油耗量是占比较大的一种变动成本；道路货运的产出因素体现为道路货运活动所实现的货物周转量。为同时表征甩挂运输车辆调度模式的运输效率和节能减排效果，选取“吨公里CO2排放量”作为目标函数。该指标越高，说明道路货运的效率越低，节能减排效果越差。 与VRP问题和TTRP问题目标函数通常采用的总运距或变动成本等规模类指标不同，吨公里CO2排放量是表征货运行业CO2排放效果的基本指标[15]，属于效率类指标。在我国甩挂运输试点工作中，各企业甩挂运输试点方案的评价指标之一就是CO2排放量，本文选用该指标可使研究结果尽可能贴近我国甩挂运输企业实践。此外，该指标是一种相对指标，便于进行不同算例计算结果的横向比较。 LTDP问题数学模型涉及两类决策变量：表示编号为k的牵引车在弧(i,j)上拖挂行驶的次数，为0到dmax间的整数；表示编号为k的牵引车在弧(i,j)上独自行驶的次数，为0到dmax间的整数，其中dmax为货运需求的最大值。 目标函数：min ,(1)(2)(3)(4)(5)(6) 式中，为整数；i,j=0,1,2,…,n; i≠j；整数k的最大值为最终方案所用牵引车总数H，且dijrij)/D2。 γ为依据联合国政府间气候变化专门委员会提供的CO2排放量计算方法所使用的排放系数；与分别为第k台牵引车独自行驶或拖挂半挂车行驶于vi与vj间的燃油消耗量；W为半挂车载货量；设牵引车行驶速度恒定，则网络节点间运距和行驶时间矩阵一致，记dij为vi与vj间的运距；η1,η2分别为满足货运需求上限和下限的比例系数；记牵引车路线的运距范围在D1与D2之间。在牵引车行驶速度确定的情况下，运距范围与驾驶员的工作时间范围一致。 约束条件(1)要求货运需求满足率处于一定范围内，约束条件(2)～(4)确保路径闭合与度平衡，约束条件(5)与(6)为路径长度约束。 2.2 算例 既有相关研究工作提供了若干基准算例及其最优解，本文依据目前可获得的这些算例的最优方案，估算最优方案下各个算例的吨公里CO2排放量。采用以下基准算例作为参考：(1)Christofides等[16]提供的14个VRP问题基准算例。(2)Fisher等[17]提供的6个有容量约束的车辆调度问题(Capacitated Vehicle Routing Problem,CVRP)问题基准算例，Christofides 等[18]提供的13个CVRP基准算例，Russell等[19]提供的4个CVRP问题基准算例，以及Christofides等[16]提供的4个CVRP问题基准算例，共27个CVRP问题基准算例。由于不同学者采用不同求解方法所获得的某基准算例的最优解不同，某基准算例可能有多个估算结果(图1给出了33个估算结果)。(3)Chao[4]提供的21个TTRP问题基准算例。值得注意的是，上述基准算例一般采用总运距作为目标函数，所以其最优方案极有可能与以吨公里CO2排放量为目标函数的最优方案有明显不同。从估算结果看(图1)，上述算例最优方案的吨公里CO2排放量主要分布在60～140 g/(t·km)之间，且其平均值较为接近。此外，上述算例最优方案的总运距波动范围则在100～1 900 km之间。可见，以总运距作为对比指标时不适宜各类算例求解结果之间的横向比较。
图1 既有相关研究中各类基准算例最优解的吨公里CO2排放量估计Fig.1 Estimation of CO2 emissions per ton kilometer of different benchmark instances in existing related researches 注：各类算例的编号是本文拟定的，每个编号的算例对应于本文所采用的某基准算例。
能够确定城市节点间货运需求量是设计LTDP问题实践算例的基本条件。本文参照文献[20]提供的城际干线运量估算数据，以山东省17个地级城市为网络节点，以高速公路为网络的边，抽象设计若干LTDP问题实践算例。在这些算例中，以17个地市中的某城市作为中心场站、其他16个地市作为客户点，可得到17个不同的算例，这些算例的不同求解结果也反映了不同城市作为中心场站的优势。根据这些地市之间的货物交流量，设定某一开展甩挂运输业务的企业市场占有率，合理拟定半挂车额定载重及其实载率，可确定山东省城际干线甩挂运输网络每天需满足的以半挂车数为单位的货物交流需求。表2为本文所用算例的山东省地市节点间的载货半挂车交流量。 3 求解算法 借鉴既有VRP和TTRP问题求解算法的研究成果，采用模拟退火(SA)算法求解LTRP问题，SA算法被既有研究工作证明是可以成功解决汽车列车调度问题的一类启发式算法[6,21]。 3.1 算法主流程 LTDP问题数学模型的约束条件(5)与(6)为构造可行的牵引车运行路线的基本依据。在对算例进行试算时，采用“牵引车数量=货运需求总量/a”，式中a为经验值。在重复SA优化过程中增加牵引车数，使得货运需求满足率持续提高，可确定合适的牵引车数。 牵引车数量是求解LTDP问题SA算法的首要参
表2 LTDP实践算例的载货半挂车交流量(单位：veh)
Tab.2 Loaded semitrailers’ interchanging of practical
LTDP instances (unit: veh)
济南青岛淄博枣庄东营烟台潍坊济宁泰安济南012121310青岛1060471801淄博140122311枣庄101000001东营232001101烟台162020500潍坊3153014012济宁101000100泰安011110200威海021011100日照031001100莱芜000010100临沂123011212德州003010112聊城114010123滨州210010401菏泽101000001威海日照莱芜临沂德州聊城滨州菏泽济南00010121青岛33121110淄博10033301枣庄00000000东营00011100烟台11010000潍坊11121140济宁00011200泰安00022311威海00000000日照00000000莱芜00010110临沂00100110德州00000210聊城00102011滨州00111100菏泽00000100
数，求解结果与牵引车数量有很大关系。牵引车数量的确定方法包含最优牵引车数量Mbest的确定和最优牵引车路线方案的确定，以下是牵引车数量Mbest的算法求解基本流程。 Step 1: 取初始牵引车数量为经验值M=D/a(式中D为货运需求总量;a为经验值)。 Step 2: 根据牵引车运行路线的总运距约束构造可行的牵引车路线集合V,随机选取M条牵引车路线作为初始解X。 Step 3: 设定初温T=T0；外循环计数变量w=0，内循环计数变量q=0；货运满足率设定为解X的货运需求满足率。 Step 4: 外循环计数w=w+1。 Step 5: 内循环计数q=q+1。 Step 6: 从V中随机选取1条牵引车路线，替换X中随机1条牵引车路线，生成新的解Z。 Step 7: Metropolis准则判定(k为步长参数)。 根据Metropolis准则第1个判定条件，比较路线方案X和Z的货运需求满足率，若Δ=R(Z)-R(X)≥0，则将X替换为Z，即X=Z；若R(z)-R(X)r为0至1之间的随机数，若exp(Δ×k/T)>r，则将X替换为为Z，即X=Z。 Step 8: 计算当前解Xbest下的。 Step 9: 内循环终止判定。 内循环终止准则要求达到设定的内循环次数。若在等温下q达到内循环次数Ne，即q=Ne，则进入下一次外循环，T计数，q置零，即T=T×k,q=0；若qNe，回到Step 5。 Step 10: 外循环终止判定。 外循环终止准则要求达到外循环末温。若外循环未达到终止温度TF，即T-TF>0，回到Step 4；若T-TF≤0，终止SA算法外循环过程。 Step 11: 设R1,R2为拟达到的货运需求满足率边界。若货运需求满足率RbestR1，则使M=M+1，回到Step 2；若货运需求满足率Rbest>R2，则使M=M-1，回到Step 2；若货运需求满足率R1≤Rbest≤R2，则得到最优牵引车数量Mbest，Mbest=M。 在牵引车数量Mbest确定后，可以以Mbest为已知量进行牵引车路线方案的求解，牵引车路线方案的算法求解流程总体上与牵引车数量求解流程一致，只是在Step 1直接取牵引车数为Mbest；此外，外循环终止判定环节增加另外一种准则：若外循环获得高于R2的货运需求满足率和低于第2.1节所建模型的目标函数值Cbest，则回到Step 4；否则，终止SA算法外循环过程。 3.2 后处理 后处理过程针对SA算法求解所得的满意解，该过程是可选的，对特定算例满意解有较好的再优化效果。后处理包括两方面，一是删除空驶路段，二是对路段进行重新整合使其满足路径长度约束，具体步骤如下：(1)考察满意方案中每条路线的路段是否为牵引车独自行驶路段，将那些所包含的路段全部为这种路段的路线直接从方案中删除；(2)考察满意方案中每条路线的路段是否为这种路段，找出其所包含的路段中除了一段有普通货运，其他路段全部为牵引车独自行驶路段的路线；(3) 若将第(2)步中找出的路线删除，则为了保证需求满足率，必须把拟删除的这些路线中有普通货运的那条路段加到合适的路线上；(4)对经过调整后的最终路线方案进行统计，更新统计指标。 4 算例求解 在本文所构建的LTDP问题数学模型中，驾驶员与牵引车连续工作时间是牵引车路径优化过程的重要约束因素，这必然将模型解的可行域大大压缩。货运需求满足率可能会因货运需求分布、中心场站分布等的不同而难以达到100%。为确保获得不同算例的满意解，本文在对山东省城际干线甩挂运输网络算例进行求解时，将货运需求满足率分别设定为85%和100%两种情况。选取一汽集团生产的平头柴油半挂牵引车(型号CA4250P66K24T1A1HE)和山东鲁峰专用汽车公司生产的两轴厢式运输半挂车(型号ST9351XXY)。根据交通运输部发布的《道路运输车辆燃料消耗量达标车型表》的有关信息，当车辆行驶速度定为50 km/h时，牵引车拖挂半挂车行驶的油耗取为32 L/(100 km)，牵引车独自行驶的油耗取为18 L/(100 km)。 在山东省17个地市中，有6个地市作为中心场站时可以达到100%的货运需求满足率，这些城市包括：济南、青岛、淄博、潍坊、泰安、莱芜。总体看，这几个地市是交通区位较优、货源规模较大的城市。将货运需求满足率设为85%(在LTDP问题模型中取η1=85%，η2=86%)，则对17个算例的求解结果如表3所示。
表3 货运需求满足率为85%时各算例甩挂运输牵引车调度方案求解结果
Tab.3 Solving result of trailer pick-up transport LTDP instances when freight demand satisfaction is 85%
中心场站位置济南青岛淄博枣庄东营烟台货运需求满足率/%858585858585牵引车数/veh6254548661100总油耗/L188311774617418237891847127475货物周转量/(t·km)756318764676757026730140739671770496吨公里CO2排放量/[g·(t·km)-1]67.9763.3562.8188.9568.1797.35牵引车平均运输的挂车数/veh4.294.934.933.094.362.66中心场站位置潍坊济宁泰安威海日照莱芜货运需求满足率/%858585658585牵引车数/veh5210064697764总油耗/L171742653718993194422190318964货物周转量/(t·km)760716755100741291583566741141742938吨公里CO2排放量/[g·(t·km)-1]61.6395.9469.9590.9580.6869.68牵引车平均运输的挂车数/veh5.122.664.163.863.454.16中心场站位置临沂德州聊城滨州菏泽货运需求满足率/%8585858575牵引车数/veh6978766094总油耗/L2027522409218201825225295货物周转量(t·km)735831760380753075738381638790吨公里CO2排放量/[g·(t·km)-1]75.2280.4679.1067.48108.10牵引车平均运输的挂车数/veh3.863.413.504.432.83
除了以威海、菏泽为中心场站的算例外，其他算例的货运需求满足率均达到了85%，吨公里CO2排放量的平均值为78.11 g/(t·km)。 参考既有相关研究结论，比较全国、山东省、台湾省、美国、欧盟等国家和地区道路货运吨公里CO2排放量的平均水平，以及由本文2.2节选定的既有基准算例以总运距为目标函数的最优解的吨公里CO2排放量(图2)。可见，理论研究层面的算例优化计算结果优于实践。相对于VRP，CVRP，TTRP问题基准算例，本文算例的求解效果更好一些。原因是在基于城际干线运输过程的公路牵引车调度求解算例中，干线运输车辆吨位较大且运距较长，规模经济效应明显。
图2 各类算例的吨公里CO2排放量求解效果对比Fig.2 Comparison of solving results of CO2 emission per ton-kilometer in different instances 注：全国和山东省数据来源于文献[22]；台湾省数据来源于文献[23]；美国数据来源于文献[24]；欧盟数据来源于文献[25]。
由上述算例运算工作，有以下3点值得注意： (1)由于每个工作日内牵引车连续工作总时间决定了牵引车路径的合理长度区间，城际干线甩挂运输网络上中心场站的位置、货运需求的空间分布等因素对牵引车调度方案设计具有重要的影响，应科学权衡货运服务水平(货运需求满足率水平)和牵引车工作时间利用之间的关系。另一方面，本文的算例求解结果在一定程度上表明了中心场站选址与牵引车调度之间的密切关系，可考虑将牵引车调度方案和牵引车场站选址有机结合。 (2)在甩挂运输模式下，每条牵引车路线上拖挂半挂车的数量是重要参数之一，在一定程度上可表征运输网络上牵引车的使用效果。本文的算例求解工作表明，每条牵引车路线上拖挂半挂车约为4台；求解效果越好的算例，每条牵引车路线能拖挂的半挂车数量越多一些。企业应尽可能采取措施提高每条路线上拖挂半挂车的数量。 (3)牵引车的驾驶员配备方式对于牵引车连续工作时间具有直接影响，这也决定了牵引车调度方案的形式。城际干线运输网络可能处于城市群，也可能处于较大地理空间范围内，这就使运距参差不一。当驾驶员乘组包括2名及以上驾驶员时，每台牵引车可以服务于更多的半挂车集散点，承担更多的运输需求，也可减少牵引车的保有和使用总量。 5 结论 现阶段我国企业能够用于开展甩挂运输的车型为牵引车拖挂半挂车，这决定了城际干线运输是当前我国发展甩挂运输模式的主要应用领域。结合当前我国有关企业的甩挂运输试点实践，本文提出了以货运吨公里CO2排放量为目标函数的LTDP问题，该类问题面向“多对多”式的城际整车运输需求，尊重驾驶员工作时间和牵引车连续工作时间等实践要求。针对LTDP问题的整数规划模型，设计了基于模拟退火的求解算法主流程，并辅以可选用的、针对主流程运算结果的后处理操作。算例表明，本文所构建的LTDP问题整数规划模型及其启发式求解方法是可行的。现阶段我国甩挂运输试点企业往往在原有单体卡车运输线路的基础上将其改造为甩挂运输线路，较多采用的甩挂运输形式是“一线两点，两端甩挂”。从本文经过求解获得的牵引车路线方案看，较为理想的牵引车路线往往是若干“一线两点，两端甩挂”模式的组合，这种组合过程很复杂。在较大规模的城际干线运输网络中开展甩挂运输，一般难以用传统的、人工调度方式确定牵引车调度方案，应考虑借助运筹优化技术。 参考文献： References: [1] 李红启，高洪涛．甩挂运输操作技术与方法[M]．北京：中国物资出版社，2012． LI Hong-qi,GAO Hong-tao. Operational Technology and Method of Tractor and Semitrailer Transportation[M]. Beijing: China Logistics Press,2012. [2] SEMET F,TAILLARD E. Solving Real-life Vehicle Routing Problems Efficiently Using Tabu Search[J]. Annals of Operations Research,1993,41(4):469-488. [3] 李亚茹．提高道路运输效率的有效途径: 甩挂运输[J]．公路交通科技，2004，21(4)：119-122． LI Ya-ru. Semi-trailer Swap Transport: An Effective Way to Improve Road Transport Efficiency[J]. Journal of Highway and Transportation Research and Development,2004,21(4): 119-122. [4] CHAO I M. A Tabu Search Method for the Truck and Trailer Routing Problem[J]. Computers and Operations Research,2002,29(1): 33-51. [5] VILLEGAS J G,PRINS C,PRODHON C,et al. A Matheuristic for the Truck and Trailer Routing Problem[J]. European Journal of Operational Research,2013,230(2): 231-244. [6] BODIN L,MINGOZZI A,BALDACCI R,et al. The Rollon-rolloff Vehicle Routing Problem[J]. Transpor-tation Science,2000,34(3):271-288. [7] BALDACCI R,BODIN L,MINGOZZI A. The Multiple Disposal Facilities and Multiple Inventory Locations Rollon-rolloff Vehicle Routing Problem[J]. Computers & Operations Research,2006,33(9): 2667-2702. [8] 梁波．大型钢铁企业厂内车辆循环甩挂运输模式研究[D]．长沙：中南大学，2009． LIANG Bo. Research on Semi-trailer Loop Swap Transportation Applied in Large-scale Iron and Steel Works[D]. Changsha: Central South University,2009. [9] 范宁宁．烟大滚装甩挂运输牵引车调度优化研究[D]．大连：大连海事大学，2012． FAN Ning-ning. Research on Tractor Optimization Scheduling of Ro-Ro Left-hanging Transportation from Yantai to Dalian[D]. Dalian: Dalian Martime University,2012. [10]张磊磊．LPG循环甩挂运输调度优化研究[D]．大连：大连海事大学，2013． ZHANG Lei-lei. Research on LPG Cycle Drop and Pull Transport Optimization Scheduling[D]. Dalian: Dalian Martime University,2013. [11]BARCOS L,RODRGUEZ V,LVAREZ M J,et al. Routing Design for Less-than-truckload Motor Carriers Using Ant Colony Optimization[J]. Transportation Research Part E: Logistics and Transportation Review,2010,46(3): 367-383. [12]LI H,LI Y,ZHAO Q,et al. The Tractor and Semitrailer Routing Considering Carbon Dioxide Emissions[J/OL]. Mathematical Problems in Engineering,2013,Article ID 509160,1-12[2015-09-10].http://dx.doi.org/10.1155/2013/509160. [13]LI H,LI Y,LU Y,et al. The Effects of the Tractor and Semitrailer Routing Problem on Mitigation of Carbon Dioxide Emissions[J/OL]. Discrete Dynamics in Nature & Society,2013,Article ID 80935,1-414[2015-09-10]. http://dx.doi.org/10.1155/2013/809135. [14]HERTZ R P. Hours of Service Violations among Tractor-trailer Drivers[J]. Accident Analysis and Prevention,1991,23(1):29-36. [15]IERLAND E V,GRAVELAND C,HUIBERTS R. An Environmental Economic Analysis of the New rail Link to European Main Port Rotterdam[J]. Transportation Research Part D: Transport & Environment,2000,5(3):197-209. [16]CHRISTOFIDES N,MINGOZZI A,TOTH P. The Vehicle Routing Problem[M]//CHRISTOFIDES N,MINGOZZI A,TOTH P,et al. Combinatorial Optimiza-tion. London: John Wiley and Sons,1979. [17]FISHER M L. Optimal Solution of Vehicle Routing Problems Using Minimum K-trees[J]. Operations Research,1994,42(4):626-642. [18]CHRISTOFIDES N,EILON S. An Algorithm for the Vehicle-dispatching Problem[J]. Operational Research Quarterly,1969,20(3):309-318. [19]RUSSELL R,IGO W. An Assignment Routing Problem[J]. Networks,1979,9(1):1-17. [20]高洪涛，李红启．道路甩挂运输组织技术及其应用实践[M]．北京：中国物资出版社，2011． GAO Hong-tao,LI Hong-qi. Operational Method and Application of Tractor and Semitrailer Transportation[M]. Beijing: China Logistics Press,2011. [21]LIN S W,YU V F,CHOU S Y. A Note on the Truck and Trailer Routing Problem[J]. Expert Systems with Applications,2010,37(1): 899-903. [22]李红启．山东省甩挂运输发展规划研究[R]．北京：北京航空航天大学，2013． LI Hong-qi. Research on Developing Plan of Tractor and Semitrailer Transportation in Shandong Province[R]. Beijing: Beihang University,2013. [23]LIAO C H,TSENG P H,LU C S. Comparing Carbon Dioxide Emissions of Trucking and Intermodal Container Transport in Taiwan[J]. Transportation Research Part D: Transport & Environment,2009,14(7):493-496. [24]DAVIS S C,DIEGEL S W,BOUNDY R G. Transportation Energy Data Book: Edition 32[R]. Oak Ridge: Oak Ridge National Laboratory,2011. [25]European Environment Agency. Transport at a Crossroads-TERM 2008: Indicators Tracking Transport and Environment in the European Union[M]. Luxembourg: Office for Official Publications of the European Communities,2009. Intercity Line-haul Tractor Dispatching Problem in Trailer Pick-up Transport and Its Solving MethodLI Hong-Qi1, CHANG Xin-Yu1, ZHU Xiao-Ning2, LU Yue3 (1. School of Transportation Science and Engineering, Beihang University, Beijing 100191, China; 2. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China; 3. Beijing Huayun Traffic Consulting and Development Corporation, Beijing 100038, China) Abstract： We put forward the line-haul tractor dispatching problem (LTDP) on the background of tractor dispatching involved in intercity line-haul trailer pick-up transport. In the LTDP, the transport demand is full-truck load which exists between any two customer depots (the many-to-many demand). The continuous working time lengths of driver and tractor are regarded as the important constraints. The objective function of LTDP is CO2 emissions per ton-kilometer. We founded an integer programming model of LTDP, which is solved by a designed algorithm which takes simulated annealing (SA) as the main frame, and also provided an optional phase to improve the satisfactory solution get by the main frame. The algorithm is used to solve a realistic instance abstracted from the intercity line-haul trailer pick-up transport network in Shandong Province. The computation result shows that the the established integer programming model and the heuristic algorithm is feasible and valid, and line-haul trailer pick-up transport is more energy-efficient emissions-decreasing than truck transportation. Key words： transport economics; tractor dispatching; simulated annealing; trailer pick-up transport; line-haul 文献标识码： A 文章编号： 1002-0268(2016)02-0151-08 中图分类号： U492.3+31 doi:10.3969/j.issn.1002-0268.2016.02.023 作者简介：李红启(1977-)，男，山东平度人，博士后.([email protected]) 基金项目：国家自然科学(71202016) 收稿日期：2014-07-18
货车调度篇二:MIT新算法助力共享汽车调度系统，如何减少75﹪的城市车辆？
交通拥堵不单让司机师傅们惟恐避之不及，更加对公共健康和国家经济造成了巨大的负面影响。
有研究指出，美国2015年度由交通拥堵造成的经济损失高达1600亿美元，其中包括70亿小时白白浪费在车流中的等待时间，以及30亿加仑发动机空载消耗的化石燃油。
当前，治堵的一个有效方法就是如滴滴、Uber这样的共享汽车。但共享汽车究竟能达到怎样的治堵效果，此前并没有一个基于数据出发的科学评估。
近期，MIT计算机科学与人工智能实验室（CSAIL）研发了一套全新的共享汽车调度系统，不但大大增强了现有共享汽车的运行效率，同时从数据上证明了共享汽车在治疗城市交通拥堵上的卓越表现。
CSAIL的研究表明，在不增加额外出行时间的情况下，使用共享汽车可以减少约75%的城市车辆。具体的说，在纽约只需要3000辆四座汽车提供的共享汽车服务就可以取代98%的城市出租车，而且前者的平均等待时间只需2.7分钟。
这项研究的负责人，CSAIL实验室的主任Daniela Rus教授在2016年8月曾出席雷锋网主办的CCF-GAIR大会，并发表人工智能相关的主题演讲。对于这项最新研究，她表示：“通过共享机制，每一辆四座汽车都可以一次运送多位乘客（而不像出租车那样一次只能运送一位），对于司机来说，这意味着耗费更少的时间、更少的车次，却可以获得同样多的收入。当然，这也同时意味着更少的交通拥堵，更少的空气污染，以及更快捷的出行体验。”
研究还指出，只需要2000辆10座商务车就能覆盖纽约市近14,000辆出租车提供的95%的出行服务。
据Daniela Rus教授介绍，基于纽约市大约300万辆出租车提供的数据，他们最新研究的调度系统可以实时的根据乘客目的地的变更重新规划行车路线，而且还可以主动调度空闲的共享汽车到出行需求较大的地区，通过这些手段，相比于现有调度系统大约可以提升20%的运行效率。
CSAIL新系统的大致工作原理是：首先将所有的用户请求和车辆情况绘制出来，形成图表，然后遍历所有可能的行程组合，并绘制出第二张图表，最后利用被称为“整数线性规划”的算法从图表中计算出最合理的组合。更重要的是，在订单分配之后，系统还可以根据剩余的空闲车辆的情况以及不同地区的出行需求重新调配，以平衡各地区的需求和空闲车辆数。
Daniela Rus教授表示：“新系统开发中最关键的挑战在于，既要管理成千上万的共享车辆和用户订单，还要保证实时的计算结果。最终我们之所以能做到这一点，都要归功于上述第一张图表的帮助，这张图表使我们能够详细理解并最终抽象出整个城市的道路交通网络。”
Daniela Rus教授将最终的产品命名为“任意时间优化算法”（anytime optimal algorithm），意指它运行的次数越多，表现就越好，在任何时间都能提供当前条件下的最优解。Daniela Rus教授说，她迫不及待的想看到这一算法通过不断的自我提升最终能达到怎样的精度。
其实，国内企业滴滴已经将人工智能技术成功应用在了自家的汽车调度系统中，大大提升了运行效率，其具体原理详见《滴滴研究院副院长叶杰平：揭开滴滴人工智能调度系统的真面目》。
Daniela Rus教授表示：“据我们所知，CSAIL的这项研究是业内首次将车队规模、载客量、等待时间、出行延迟和运营成本在实验室进行综合的量化，包括出租车、大货车和接驳班车等各种车型。同时，我们认为这一全新的调度系统还特别适合于未来的自动驾驶汽车，因为它可以根据实时请求连续的重新规划路线。”
其实，共享汽车（或者拼车）的概念早在几十年前就已经存在了。只不过近两年由于智能手机和移动互联网的普及，让共享汽车成为了一种更经济也更快捷的选择，因此迎来了爆发式的增长。
然而，现有的共享汽车调度系统在用户体验和便捷性上还有待提升。例如，有些系统要求用户B的上车地点必须在用户A的路径规划途中，并且双方都要在订单创建之前就提交所有请求。
相比之下，CSAIL的新系统允许不同乘客的订单重新匹配到不同的车辆。同时，这一系统还可以分析各种不同车型的特点，根据分析结果进行灵活调配。例如，10座商务车在什么时间和什么地点更容易接到合适的订单，就跟普通的4座汽车完全不同。
“共享汽车对于城市的交通拥堵、环境污染和能源消耗等各方面都具有非常大的积极影响，”Daniela Rus教授说：“作为一名科研人员，尽可能的去探索各种方法来提高交通系统的运行效率和可靠性，这一点非常重要。”
据悉，该研究成果将发表在本周出版的国家科学院院刊（PNAS）上。
货车调度篇三:报告 | 中国物流发展报告（2015—2016）陆运篇
经历了行业的起步、累积阶段，目前已经进入行业整合，市场集中度迅速增加的集中阶段。预计从2020年开始，行业完成洗牌，大竞争者联盟，小的被并购或死亡。
物流行业，自古以来就承担着让社会物资流动的重要使命。从古代的镖局到今天的快递，虽然效率、方式、载体一直在变，但是实质并没有变：那就是通过物资的流动，促进整个社会的发展。
根据中国物流与采购联合会、中国物流学会编辑出版的《中国物流发展报告（2015—2016）》数据显示，2015年，社会物流需求呈稳中趋缓态势，全国社会物流总额219.2万亿元，比上年增长5.8%，增速回落2.1个百分点；社会物流总费用与GDP的比率为16%，比2010年的17.8%有较大幅度下降。
其中的原因有：
公路货运量、货物周转量、GDP数据的调整；
产业结构调整、物流服务价格下降；
物流运行效率有所提升。
尽管2015年我国物流业增长速度持续放缓，但物流业总收入达7.6万亿元，比上年增长4.5%。全国货运量417亿吨，快递业务量突破200亿件，冷链物流市场规模预计超过1500亿元。预计2016年物流业整体呈现“缓中趋稳”的发展态势，全社会物流总额预计增长6%左右，物流业总收入预计增长4%左右。
陆运
陆运主要分为铁路运输和公路运输，这是目前最常见的物流方式。
（一）铁路运输
现状：随着我国经济发展进入新常态，铁路货运市场持续低迷，2014年全国铁路累计完成货运量38.1亿吨，同比下降3.9%，铁路货运量在全社会货运占比降至8.7%，为近年最低。2015年货运量继续下滑，1-5月累计完成铁路货运货运发送量14.3亿吨，同比下降9.8%。
玩家：参与物流运输的主要是中铁总局、中铁铁龙、广深铁路等有铁路资源的国有企业，民营企业很难参与进去分一块蛋糕。
问题：中铁总局、中铁铁龙等公司同样面临主体间协作能力较弱、服务功能单一、在整个物流市场缺乏核心竞争力等问题。
（二）公路运输
现状：互联网货运受到一级市场热捧，去年上半年部分重要的物流投资案例中，融资金额超过1亿元人民币的有9个，其中主攻车货匹配的有4个，但是在2016年，货运行业的融资热度有所下降。
互联网货运平台百舸争流，运输管理的平台化是未来突破方向：国内已经有超过200多个车货匹配类APP，主要分为2类：纯平台模式和线上结合线下模式，基本覆盖了所有的关键物流环节，并且新产品更多地集中在信息匹配，管理与交易领域。
玩家：民营企业占主导地位。
根据距离划分，可分为城际物流和同城配送。
1.城际物流：
顾名思义，城际物流解决的是城市与城市之间的货物流动问题，在这个领域，玩家主要分为三个类别。
A. 企业自建物流
代表：海尔集团的日日顺，电商领域的京东、苏宁等
B. 第三方物流
代表：志鸿物流、德邦、安能等
C. 快递公司
代表：四通一达、顺丰等
城际物流目前主要的玩法是：用互联网去解决车货匹配的问题，缩短货车的等货物的时间，降低货车的空驶率，提升整体运营效率。
但目前为止，城际货运仍然存在以下问题：
信誉问题：中间的物流平台没有把好关，导致车货双方互不信任，存在欺骗现象；
信息不对称：成绩货运行业普遍存在车比货多的现象，导致一些车辆在等待中浪费时间和金钱，因此有效的信息连接仍然没有建立；
难以形成规模优势：众所周知，城际物流走向盈利在于要整合碎片化的需求，实现规模化，但是目前整个行业还是比较散乱的。
2.同城物流
同城物流就像一座城市的毛细血管，一座城市所需的消费品通过弯弯曲曲的城市道路，经由一辆辆三轮货车，被送到消费者手中。如果没有同城物流和末端配送，前期的物流工作将无法转化为成果，因此同城物流是盘活一座城市的重要方式。
目前同城物流的配送效率越来越高，但总体存在着以下问题：
空载率等浪费运力的现象普遍存在；大公司模式趋同，低价竞争；
众包模式依旧无法停止补贴，难以盈利；行业服务没有标准化，存在安全隐患；
在生鲜配送环节，缺乏技术创新等等。
按照目前细分的领域，同城物流主要分为4个类别：
a. 传统类
代表企业：“四通一达”、顺丰、德邦等
概述：从桐庐起家后，“四通一达”的业务迅速发展，尤其是借势电商，让中国的快递行业都冲向巅峰。2014年，全国快递服务企业累计业务量达到140亿件，这是我国快递年业务量首次突破百亿，并跃居世界第一。
问题：近两年来，“四通一达”的发展陷入了共同的漩涡——低价薄利，恶性竞争。
现状：虽然整个蛋糕很大，但是这几个主要玩家的实力并没有明显差距：商业模式、盈利方向、市场战略都高度趋同，为了在这场竞争中取胜，包括顺丰在内的快递企业都扎堆上市，借助资本的力量，应对成本上升，利润下降的局面。
利用快递专家赵小敏的话来解释，“上市除了能增强融资能力，还为企业提供了跨界收购等更多出路”也许再好不过。
以申通和圆通近期发布的财报看：
2015年1-9月，申通实现利润7.73亿元。按照申通超过20万的员工规模，每人每天为公司创造利润约为14元。但申通的总资产达35.8亿元，平均到每个员工身上，每个员工得到投资17895元，可见资金的投入产出比很低。
同样的问题，在圆通身上也有体现。2016年1-3月，圆通实现盈利2亿元，而圆通拥有跟申通相近的人员规模，在总资产上还高于申通。
融资状况：
总结：
这一赛道都是从仓储到运输到配送的大玩家，因此必须要依靠巨大的资金流。主要的货源集中在电商这一端，为了接到更多的订单，已经陷入低价竞争漩涡，难以确保竞争优势，因此纷纷上市，增强融资能力，寻找更多出路。
机会：
随着菜鸟的调控作用凸显，今年世界互联网大会上，菜鸟CEO童文红提出的“智能、数据、协同”将让平台上的所有快递公司提升效率，解决库存压力。因此，这个赛道上，新入局的玩家几乎没有机会，一方面是投入很大；另一方面，对手经过20年的积累，已经划定了市场格局。
b. 冷链类
代表企业：黑狗、极客冷链等
概述：数据显示，2015年，我国生鲜电商交易规模达560亿元，预计到2018年交易规模将达到2300亿元。去年，冷链物流总额约为4万亿元，年增速达22%。随着生鲜电商的迅猛发展以及冷藏食品消费量的不断提升，我国冷链物流增量空间将打开。机构预计，到2020年冷链物流市场规模将达到4000亿元。
问题：
冷链主要用来运输农产品和生鲜，但是一直以来，这类产品的运输存在这样的问题：
农产品的流通极度分散：从农民到消费者，中间经过物五六道交付环节，每个环节都势必造成损耗。根据数据显示，中国农产品，特别是果蔬类产品从产地到餐桌的损耗率接近30%，在欧美和日本，这一数字是5%。如何减少中间环节，降低损耗是难题之一。
农产品是单位重量和体积货值最低的产品：同样一辆车，装满白菜和手机的价值是不一样的，但是运输成本却是一样的，这种情况下，人们往往不会采用冷链的方式。
融资状况：
总结：
这个类别再今年几乎没有新玩家入局，因为已有的玩家还没有摸索出特别清晰的盈利模式，也没有稳定的、大规模订单。可以看到资本对这个赛道的态度还是趋于冷静的——快行线获得千万级别融资，是因为其母公司有10余年城市冷链积累，兄弟公司有浓重的“商贸基因”。资本方希望通过合作，重点发力农产品供应链。
机会：
尽管面临高损耗问题，但是随着国家政策的支持，以及居民对生鲜产品的需求逐渐旺盛，冷链运输和宅配市场或许还存在以下机会：
针对农产品和生鲜产品流通中的交接环节，完善冷链物流体系；
研发和提升冷链技术与装备；
利用大数据，提升交接环节的协作水平，降低运输和库存成本。
c. 众包类
代表企业：达达、人人快递、点我达等
概述：移动互联网时代，O2O迅速在国内兴起，餐饮、零售都在朝着线上线下的深度融合和无缝对接迈进。但是同城配送中，最后1公里的问题开始凸现出来。这部分业务需要直接面向用户，而且路线复杂，意外状况比较多，令物流公司头疼。
想要保证服务质量和效率，自建物流是个不错的办法，但是这会极大地增加成本，于是以信任为基础的众包模式不知不觉间成为了解决同城配送的最佳方式。
问题：
共享经济下的众包模式至今仍然在被质疑，法治监管如何落地，如何在给企业空间和给用户安全的区域寻求平衡发展。
运力持续性难以保障：众包平台的单量高峰是中午和傍晚时段。如何保证这两个时段平台上有足够多的配送员，而在闲时又能解放配送员也是一个问题。
盈利模式：虽说众包是降低企业运营成本的手段，但是前提是平台必须要解决效率和规模化问题，让个人和企业资源都能得到高效利用。否则停止补贴后，这个模式很难走得下去。
融资状况：
总结：
人人快递、新达达、点我达等公司把众包物流的模式推红了，但是要想走得更远，众包物流难以取消的补贴称为痛中之痛。达达和京东到家的合并说明，即便背后有雄厚的资金实力，众包物流在现阶段也必须借助伙伴，进行转型探索。
机会：
以新达达为代表的先行者已经占领众包市场，尽管他们仍然暂时摆脱不了补贴，但是已经入局的资本，和众包领域的前景，使得他们会稳步发展下去。对于新入局的玩家来说，残酷在于：如果没有革命性的模式，很难得到投资；没有投资，没有补贴，就没有任何竞争力。
d. 货运类
代表企业：58速运、易货嘀、蓝犀牛、货拉拉等
概述：同城货运出现得很早，尤其在人口比较密集的大城市，货运、搬家的需求很旺盛。在互联网介入之前，这个行业主要是在路边趴活，从A地送到B地，就又在B地趴活。总之效率极低，服务质量也价格也没有标准。互联网的运用，让司机和用户都因为信息的连接，而得到了便利。司机提升了效率和收入，用户节省了时间和成本。
问题：
如何合理调度货车资源，提升平台单量，取得用户的认可。
盈利模式单一，在现阶段还要依靠补贴，当补贴停止或降低后，货运业务本身能否盈利？不能盈利的话，公司新的业务增长点在哪里？
融资状况：
总结：
同城货运实际上是货运版的滴滴，市场上存在过刷单、烧钱现象，行业洗牌逐渐开始。但是留下来的公司在结束补贴后，还没有清晰的盈利模式，总之，这个市场目前在摆脱烧钱，同时寻求新的业务线——这条赛道上，从2015年开始，就鲜有新选手入局，说明探索阶段的玩家已经足够，而颠覆式的模式还未出现。
机会：
随着城市规模的不断扩大，同城货运市场会越来越红火，但是货车资源是既定的。新来者如何立足，主要取决于能否从别的平台瓜分货车资源。而B端市场，需求旺盛的企业已经有自己的物流队伍，同城货运很难接到大量的货物集中订单。
未来的机会或许可以在更细分的领域，比如专门针对家具、服装市场服务，定制适合目标产品的软硬件服务，提升竞争力。
（
（来源：皮擦擦 品途网 管理大数据）
