基于价值运输的多物品多集散点车辆路径问题研究

摘要：为了更好的研究多集散点车辆路径问题，本文提出了基于货物运输价值分类的多物品多集散点车辆路径问题，并针对该问题提出相应的基于承运人运输价值最大化的价值运输方法，制定了其运输规则。通过分析，该方法能够有效地解决该问题。

关键词：价值运输；多物品多集散点；车辆路径问题

中图分类号：C35文献标识码： A

1.引言

车辆路径问题（Vehicle Routing Problem VRP）最早是由Dantzig和Ramser于1959年首次提出的。它全面融会了经济科学、技术科学及管理科学，揭示了运输、储存、装卸搬运、包装、流通加工、物流信息等要素的内在联系。近年来，国内外专家学者对VRP的研究的多集中于单一车场单一物品的研究，较少的关注多车场多种物品共同运输情况下的车辆路径问题。在运输过程中，大都基于货物是同质物品的假设。而现实的运输过程中，运输的货物在其运输的过程中给承运人所带来的收益却是不同的，本文从这一角度出发，对货物进行运输价值的分类，并基于承运人是理性经济人的前提下，对多物品多集散点车辆路径问题研究。

2.基于价值运输解决多物品多集散点车辆路径问题及模型

多集散点任务可分多车辆问题界定如下：有m个需要服务的客户点,记作集合V，这m个客户点可以作为某个货物运输任务的起点，即有发货任务，也可以作为某个货物的终点，即有收货任务，也可以两种任务兼而有之；并且对于每种任务而言，每个客户可以有不止一个任务。作为有发货任务的客户可以拥有一种或多种货物，每种货物发往一个目的地。有n辆车进行货物的运输，每辆车在发货点根据利益最大化原则，对承运的运输货物进行选择。在客户点的某种货物，记作，其中分别表示起止地点，表示物品的重量，表示承运物品所获得的收益。要求合理安排路线，使得完成任务的前提下，总的行驶距离最短。

根据以上描述对多集散点任务可分多车辆问题做出如下假设：

① 车辆的容积是一样的，并且容量限制以货物的重量限制。

② 在每个发货点，车辆装载的运输量不得超过车辆的额定载重量

③ 客户点的相对位置是已知的，即两两客户点之间的距离已知。

④ 各个客户点的发货和接货任务已知，并且每次任务变动后的相应信息可及时掌握。

⑤ 车辆在完成任务后不需要返回初始出发点

⑥车辆的单位运输距离的费用与距离成简单的线性关系。

建立模型如下：

目标函数：

(1)

约束条件：

(2)

(3)

其中，

表示客户点集合，表示车辆集合，表示货物种类集合

表示客户点到客户点的距离，

表示车辆在客户点装载的货物的重量，

表示车辆的额定载重量，

表示在车辆开往客户点时的载重量

此模型中，

（1）式表示运输的目标是总路径最短。

（2）式表示车辆在客户点所装载的货物不得超过其额定载重量。

（3）式表示车辆开往客户点时的载重量时所装载的货物不得超过其额定总量。

3.2运输过程中车辆收益及分配

车辆在运输过程中，其承运人为了获得更好的收益而选择不同的货物，然而在这个过程中承运人会遇到两种情况：其一，该种货物没有经过其他车辆转运，直接运送到其目的地，完成运输任务；其二，该种货物没有直接运送到其目的地，在途中卸载，并由其它车辆完成其运输任务。那么，如何核定运送的收益和确定收益的分配时十分重要的一个问题。本文根据以上两种情况，引入如下原则来解决以上两个问题。

① 对于直接运送到目的地的任务，其承运的车辆收益为承运该任务的全部收益。即收益值。

② 对于非直接运送到目的地的任务，其最初承运车辆将其运送到客户点（），则其收益值为。其含义为，车辆获得运送货物至客户点，完成这项运输任务的比例为，那么就将获得相应的运输收益。在此之后，对于运送货物没有到达目的地的承运人也都按照这样的方法计算其运送收益。直至货物运到目的地为止。可以预见，在运输过程中是有可能出现，那么此时计算出来的收益值为负值。这是由于这个货物被运往离目的地更远的客户点，从而造成运输的无效性。将这种情况定义为无效运输。

该方案所确定的收益分配契约是按照承运人在运输过程中对于某一项运输任务的贡献率来确定其运送收益的，本着公平的原则制定的，能够为承运人所接受。

3.3价值运输法解决异种物品多集散点车辆问题运输规则

价值运输法解决异种物品多集散点车辆问题运输规则主要包括：运输起点的选择、转移点的选择和运送终点的选择构成。

① 运输起点的选择

确定了客户点的分类之后，首先要进行的就是运输起点的选择。运输起点是指车辆的第一个装货点，车辆在这个地点装载货物之后开始运送工作。车辆所处的客户点的不同,使得承运人对于运输起点的选择也不同。

根据有没有货物的运出，分为两种情况：第一种情况，当车辆处在有货物需要运出的客户点，所以为了节约行驶里程，本文假设处在这两类节客户点上的车辆直接从自身所在的位置开始进行配送，将自身所在的位置作为运输起点；第二种情况，车辆处于没有货物需要运出的客户点上，那么，车辆将从有货物运出但没有车辆停靠的客户点中选取运输起点。

为防止算法陷入过早收敛，采用确定性选择和随机性选择相结合的策略来提高全局搜索能力，即在第一步选取运输起点时，除去本身有车辆停靠的客户点，其他客户点作为随机客户点被随机选取。

② 转移点的选择

转移点的选择指的是，车辆的承运人选择哪一个客户点作为自己的下一站，以及装载哪些货物去下一站的问题。对所有承运人来说，不论是处于运输起点，还是离开了运输起点在别的节点，都面临着转移点的选择。

为更好地说明问题，先假设在客户点有种货物，这种货物记作，将以上三类客户点记为，与有非空交集。

承运人就在中选择一点作为转移点，进行选择的标准就是此次运输的收益值的大小，那么转移点的选择就变成对收益值的计算以及相应的货物选择的确定。下面以客户点为例来进行说明。

第一步，查看客户点处所有货物中以为运送目的地的货物和车上已有以为运送目的地的货物，则在不超过容量限制的情况下将所有处于客户点的货物装载到车上，并计算下当下车辆装载的物品运输到处所得到的收益。

第二步，查看在客户点其它的货物，并计算各货物运送到客户点的收益值。选取其中所有为正值的收益值，并记下相对应的货物，记作。

第三步，根据车辆的额定装载量和车辆的现装载量，计算出车辆现有剩余装载量。依据第二步的所有收益值为正的货物，找到所有不超过剩余装载量的货物组合，如等，（其中）。

第四步，计算各组合货物的的收益值之和。如组合，其运输收益值之和为。

第五步，将计算结果进行大小排序，选出最大值，将其加上，记作，并记下在客户点处取得的所需装载的货物组合，记作。

由此可得，若以为转折点进行运送，应装载货物组合。因为装载货物组合是车辆在不超过额定装载量的情况下，能够取得最大收益的装载货物组合。

通过以上五步可以车辆在确定在处以为转折点进行运送，应装载货物组合，收益值为。那么，对其他各点也采用同样的方式，确定出其它各点的收益值和相应的应装载的货物组合，并比较所有值大小进行排序，得到收益值最大的一个点，记作，并把对应记作，和相应的记作。那么，客户点就是车辆在客户点处所要选择的转运点。

③ 运送终点的选择

运送终点的选择是指，当车辆行驶到客户点处，车辆上的所有运输任务已经完成，而后在其可搜索的范围内，没有客户点有运输任务，那么，客户点就作为车辆的运送终点。

当所有运输货物运输到其目的地，所有车辆都到达其运送终点后，运输作业完成。

4.结论

本文为多物品多集散点车辆路径问题设计了基于承运人收益最大的价值运输过程。该算法从承运人作为理性经济人从自身利益出发，对不同价值的多物品做出选择，从而对货物的运输路径进行优化。该方法从实际出发，为多物品多集散点车辆路径问题提供了有效的解决方案，具有较强的理论和实际指导意义。

参考文献

[1] 杜文，李冰．多货物品种集装化运输的优化调度问题[J]．中国公路学报，2003年7月，第16卷，第3期

[2] 刘丽娜，刘宏志．城市应急救援物资运输分配模型的构建与求解[J]．信息与电脑，2011年1月

[3] 王晓博，李一军．多车场多车型装卸混合车辆路径问题研究[J]．控制与决策，2009年12月，第24卷，第12期

[4] 刘冉，江志斌等．多车场满载协同运输问题模型与算法[J]．上海交通大学学报，2009年3月，第43卷，第3期

[5] 王海宾，孙永道，柴旭光，张荣国．多车场多目标开放式物流配送车辆调度问题的研究 [J]．《计算机测量与控制》. 2010. 18(12)