多车场多配送中心半开放式满载车辆路径问题研究

　　摘 要：文章研究一个多车场多配送中心的半开放式满载车辆路径问题。在任务配送过程中需要考虑车辆的启动费用、里程限制等约束条件，在不超过车辆里程限制的基础上车辆可返回配送中心进行二次配送。建立了此类问题的数学模型，设计了解决该问题的遗传算法，并通过例子对遗传算法进行了说明。结果表明文章给出的遗传算法对解决带里程限制的多车场、多配送中心半开放式满载车辆路径问题是可行的。
　　关键词：运筹学；半开放式车辆路径问题；满载；里程限制；遗传算法
　　中图分类号：F252.14 文献标识码：A
　　Abstract： In this paper， a multi-depot， multi-distribution centers semi-open vehicle routing problem with full-truckload is discussed. In the process of delivery， the start-up cost， driving distance restriction and other constraints need to be considered， and the vehicles can return to the distribution center for the secondary distribution if their driving distances are less or equal to the driving distance restriction. An integer programming model for this problem is established， a genetic algorithm is given to solve it， and the genetic algorithm is illustrated. The results show that the genetic algorithm given in this paper to solve the multi-depot， multi-distribution centers semi-open vehicle routing problem with full-truckload and driving distance restriction is feasible.
　　Key words： operational research； semi-open vehicle routing problem； full-truckload； driving distance restriction； genetic algorithm
　　0 引 言
　　车辆路径问题（Vehicle Routing Problem， VRP）是交通运输和物流配送系统中非常重要的问题，而对于大型的生产制造企业、煤炭运输业等，由于被运输的货物需求量非常大，通常进行的都是整车运输也就是满载车辆路径问题。
　　满载车辆路径问题是NP难问题，由Ball等人[1]首次提出，到目前为止国内外对此类问题已进行了一定的研究，根据现有的文献，满载车辆路径问题按配送层数大致可归为三类：
　　（1）两层配送型：车辆从车场（或配送中心）直接装货出发，去往需求客户点送货之后返回原车场，郭海湘等[2]就研究了此类问题。
　　（2）带有重载点的两层配送型：车辆从车场空车出发，去往每个客户指定的装货点取货，再给相应的客户（卸货点）送货。将每对装货点和卸货点称为一个重载点，如文献[3-14]讨论的都是两层重载点问题或者是该问题的变种。此类问题现今研究的较多。
　　（3）三层配送型：车辆从车场空车开往配送中心，在配送中心装货去往需求的客户点送货。如：陈新庄等人[15]研究的多车场多配送中心满载车辆路径问题：车辆从车场出发可以去任一有能力的配送中心取货送往需求客户，完成配送任务后要求车辆返回原车场，范昌盛等人[16]将该问题扩展为车辆完成配送任务后不必返回原车场，但要保证各个车场派出和返回的车辆数相同的半开放式问题。三层配送问题研究相对较少，但随着信息技术的发展和经济全球化趋势，越来越多的产品在世界范围内生产、流通、销售和消费，使得物流活动日益庞大和复杂，两层配送方式已不能完全满足社会需要，应运而生的第三方物流、电子商务等，使得三层物流配送问题变得越来越重要了。
　　本文在范昌盛等人[16]研究的三层配送车辆路径问题的基础上考虑了车辆的启动费用以及各车辆配送线路长度相差不要过于悬殊等因素，将问题扩展为带车辆启动费用和车辆里程限制的半开放式满载车辆路径问题，即要求车辆在不超过其里程限制的基础上可以从客户处再返回配送中心进行二次取货，之后给有需求的客户进行配送，这样不仅减少了车辆的使用数量，降低了费用，还使得司机的工作时间及车辆的使用比较均衡，从而使配送方案更符合实际需要。
　　1 问题描述
　　在一个连通的运输网络上有n个节点，其中节点1，2，…，m为车场，m+1，…，m+p为配送中心，m+p+1，…，m+p+qn=m+p+q为客户。设各车场车型都相同，且第ii=1，…，m个车场停有a 辆车，而第jj=m+1，…，m+p个配送中心存储的货物量可以供给b 辆车整车运送，客户点kk=m+p+1，…，m+p+q需要c 辆整车的货物满足其需求。
　　车辆从其所在车场空车出发到某一配送中心取货送至某客户处，之后它可以直接返回某车场（这种车辆被称为不带返回的车辆），也可再返回到某一有能力的配送中心取货送给某个需求未满足的客户然后返回某车场（这种车辆被称为带返回的车辆），要求各车场派出与返回的车辆数相同。
　　本文将不带返回车辆所行驶的最大里程设为车辆的里程限制，各个被使用车辆在不超过里程限制的基础上，可返回有能力的配送中心进行二次配送，并且它们都有相同的启动费用。求一个满足上述要求的配送方案，使得所有被使用车辆总的行驶费用和总的启动费用之和最小。   2 数学建模
　　其中：（1）式右侧第一项为所有被使用车辆从所在车场出发到相应配送中心的总空车行驶费用与总启动费用之和；第二项为车辆从配送中心满载货物出发到客户处所有车次的满载行驶费用；第三项为所有被使用车辆从客户点出发返回车场的空车行驶费用。（2）式表示从各配送中心发出的货物数量不超过其存储量。（3）式表示到达用户的车辆次数等于其需求量。（4）式表示各被使用车辆行驶里程不超过里程限制。（5）式表示各车场发出与返回的车辆相同。
　　3 遗传算法设计
　　因本文的问题允许车辆进行二次配送，而且还考虑了车辆的启动费用和里程限制，所以范昌盛等人[16]论文中的算法不能解决此问题，本文给出下面的遗传算法来求解它。
　　3.1 生成初始种群
　　种群规模设为含100条染色体。
　　（1）节点间的最短距离
　　用Floyd算法求原始运输网络中任意两点i、j之间的最短距离，同时得到从节点i到节点j的最短距离路径。
　　（2）可行解的类型
　　将本文所讨论问题的一个可行配送方案称为其一个可行解。在一个可行解中，如果所有使用车辆都是不带返回的，就称该解为不带返回的可行解，若至少有一辆是带返回的，就称该解为带返回的可行解。
　　（3）染色体的编码
　　每一条染色体由两部分组成，第一部分为问题的一个可行解（可能是带返回的，也可能是不带返回的），第二部分为该可行解的适应值。
　　设c=c +…+c 为所有客户总的需求，本文用MATLAB实现遗传算法，为此用一个c行6列的矩阵存储一个可行解：该解中不带返回车辆的路径用该矩阵的一行来表示，该行的第1到第6个元素依次存储0、该车辆出发车场序号、到达的配送中心序号、到达的客户序号、返回的车场序号、该车经过上述节点的总行驶里程，而该解中某一带返回车辆的路径用这个矩阵的两行来表示：这两行的第1行6个元素依次存储1、该车辆出发车场的序号、到达的配送中心序号、到达的客户序号、0、经过上述节点的行驶里程；第2行6个元素依次存储2、该车第一次到达的客户序号、该车辆返回的配送中心序号、到达的客户序号、返回的车场序号、经过上述节点的行驶里程。例如：本文第4节给出的例子中有2个车场、3个配送中心、7个客户，客户总需求为10整车，下列两个10行6列矩阵（表1、表2）分别表示该实例的一个不带返回和带返回的可行解。
　　表1与表2中第1个元素为0的各行分别对应一不带返回的车辆及其路径，例如表1的第一行对应一车辆，该车从车场1出发到配送中心3取货，将货物送到客户点9之后返回车场1，这之间总行驶里程为6；表2中第一个元素为1、2的两行对应一带返回的车辆，即表2的第1、2行，第3、4行，第6、7行分别对应一带返回的车辆及其路径，比如表2的第1、2行对应一带返回的车辆其路径为：该车从车场1出发到配送中心3取货，将货物送到客户点9处，这之间该车行驶的总里程为5，之后该车返回到配送中心3取货，将货物送至给客户点8处，最后返回车场1，这之间行驶的总里程为5，于是该车行驶的总里程为10，因此表1共使用10辆不带返回车辆，表2共使用7辆车，其中4辆是不带返回的，3辆是带返回的。
　　用一个1行2列的元胞数组来存储一条染色体：该元胞数组的第1个元素存储一个可行解，第2个元素存储该可行解的适应值。
　　每条染色体适应值的计算方法为：先求出该染色体对应的可行解中所有车辆总的行驶费用与总的启动费用之和C，那么该染色体的适应值为1/C。
　　（4）带返回可行解的生成方法
　　先根据问题的条件诸如车场、配送中心的个数及它们的能力，客户的个数及其需求，随机生成一个不带返回的可行解，如表1所示，将该可行解中所有车辆的最大行程作为里程限制，在表1中第4、第7、第10行对应的车辆的行驶里程最长都是16，将16作为里程限制，将该可行解的各行按最后一个元素（各行对应车辆的行驶里程）从小到大顺序排列，例如对表1实施该操作后得表3：
　　在表3中，根据里程限制判断第10行对应车辆的配送任务能否交由第1行对应的车辆来完成，即判别第1行的车辆能否在给客户9送完货之后再返回某一有能力并且离客户点9和客户点8路程之和最小的配送中心取货，将货物送至客户点8处再返回某一车场（要保证所有车场收发车数目相同）而总的行程不超过16，如果能，就将第10行对应的车辆删除，而将其配送任务交给第1行对应的车辆完成，此时第1行对应的车辆送两次货：给客户点9和客户点8送货，该辆车就由不带返回的车辆变为带返回的车辆，如果不能就对第9行对应的车辆进行判别，如此下去直到在第2行到第10行中找到第一个符合要求的行或第2行到第10行对应的车辆都不符合要求为止，在表3中第10行对应的车辆符合要求，于是它的配送任务就交由第1行对应的车辆来完成，而表3被修改为表4。在将表3修改为表4的过程中，表3的第2至9行的内容有可能被修改，这是因为需要保证各个车场收发车的数目相同所致，如果被修改了，就将表4中第3至10行按最后一个元素（行驶里程）从小到大进行排列，之后对表4的第3行实施对表3的第1行同样的操作，…，最后得到表2这个带返回的可行解，将该可行解与其适应值放在一个1行2列的元胞数组中作为一条染色体。
　　用上述方法生成100条染色体，将它们存储到一个100行2列的元胞数组中作为初始种群。
　　3.2 个体的选择
　　用轮盘赌在父代中随机选择子代的个体，并使用精英保留策略， 即用父代的最好解代替选择操作后得到的最差解。
　　3.3 交叉和变异
　　交叉：取交叉概率为0.6，对满足交叉概率的两条染色体还需满足下列条件才进行交叉：它们对应的两个可行解中：（1）都有不带返回的车辆，（2）在不带返回的车辆中都有出发车场与返回车场相同的车辆，（3）在满足（1）和（2）的车辆里能各选出一辆，使得这两辆车对应的车场和配送中心都有能力，那么这两条染色体就可以交叉：交换两辆车的车场和配送中心，客户保持不变，并重新计算总里程。   例如：表5也表示本文第4节例子的一个可行解（带返回的），该解与表2表示的可行解满足上述条件（1） （3），这是因为表2的第9行与表5的第10行分别为：
　　交叉后这两行依次变为：
　　变异：取变异概率为0.4，对满足变异概率的染色体，将其对应的可行解中第1个元素为0或1的行中第3个元素（配送中心）进行修改：在有能力的配送中心中寻找一个使其到这些行对应车辆出发的车场和送货客户总行程最近的配送中心，用它去替换该行的配送中心，例如在表5中，第1、第3、第4、第6行，第8到第10行的第3个元素（配送中心）都要做修改，比如第3行需要在有能力的配送中心：3、5中寻找一个到车场1和客户点6总的行程最近的配送中心来替换配送中心3，表5经变异操作后变为表6。
　　4 例 子
　　本文采用文献[16]的例子：某一有12个节点的网络（如图1所示），图1给出了原始运输网络的连接状况和相邻两节点间的距离。
　　在图1中，节点1、2为车场，3、4、5为配送中心，6 12为客户，表7给出了每个车场拥有的车辆数、每个配送中心存放的货物数（整车）和每个用户点需要的货物数（整车）。
　　设每辆车的启动费为3，当λ =λ =1时，运行第3节给出的遗传算法后得到该例子的一个次优解，该次优解一共使用了5辆车，即一共有5条路径如表8所示。
　　这5条路径的长度依次为：14，12，12，16，13，因此5条路径的长度之和为67，该次优解其目标函数值为：3 5+67=82，其中3 5是5辆车总的启动费用。
　　文献[16]得到的本例的次优解一共使用10辆车，即一共有10条路径如表9所示，这10条路径的长度依次为：4，6，6，6，6，6，12，7，10，9，得10条路径的长度之和为72，该次优解的目标函数值为：3 10+72=102，其中3 10为10辆车的总启动费用。
　　表8中第1条路径的含义是：车辆从车场1出发，经车场1到配送中心4的最短路径1 4到配送中心4取货，再经配送中心4到客户点7的最短路径4 7给客户点7送货，之后经客户点7到配送中心5的最短路径7 12 5返回到配送中心5取货，再经配送中心5到客户点12的最短路径5 12给客户点12送货，最后经客户点12到车场1的最短路径12 7 1返回车场1， 同理可得表8中其它路径以及表9中各条路径的含义。
　　对上述两个次优解比较发现：本文得到的次优解：（1）车辆使用数量少；（2）各条线路长短比较均衡，因此各辆车的使用量以及司机工作量大致相同，更符合实际需求；（3）目标函数值小，结果更优。
　　5 结 论
　　本文利用遗传算法解决了一个带里程限制的多车场、多配送中心半开放式的满载车辆路径问题，并要求车辆在不超过其里程限制的基础上允许返回配送中心进行二次配送。通过例子对本文的问题及给出的遗传算法进行了说明，通过比较发现，本文的问题更符合实际配送需求，给出的算法得到的结果更优。
　　参考文献：
　　[1] Ball M， Golden B L， Assad A A. Planning for truck fleet size in the presence of a common-carrier option[J]. Decision Science， 1993（14）：103-120.
　　[2] 郭海湘，杨娟，等. 带服务优先级的煤矿资源配送车辆路径问题[J]. 系统管理学报，2012，21（1）：133-144.
　　[3] 郭耀煌，李军. 满载问题的车辆路线安排[J]. 系统工程学报，1995，10（2）：106-118.
　　[4] Arunapuram S， Mathur K， Solow D. Vehicle routing and scheduling with full truckloads[J]. Transportation Science， 2003，37（2）：170-182.
　　[5] Gronalt M， Hartl R F， Reimann M. New savings bas-ed algorithms for time constrained pickup and delivery of full truckloads[J]. European Journal of Operational Research， 2003，151（3）：520-535.
　　[6] 刘冉，江志斌，陈峰，等. 多车场满载协同运输问题模型与算法[J]. 上海交通大学学报，2009，43（3）：455-459.
　　[7] 霍佳震，张磊. 用节约法解决带有时间窗的满载车辆调度问题[J]. 工业工程与管理，2006，11（4）：39-42.
　　[8] 孙国华. 带软时间窗的开放式满载车辆路径问题研究[J]. 计算机工程与应用，2011，47（17）：13-17.
　　[9] 孙国华. 带时间窗的开放式满载车辆路径问题建模及其求解算法[J]. 系统工程理论与实践，2012，32（8）：1801-1806.
　　[10] Liu R， Jiang Z， Liu X， et al. Task selection and routing problems in collaborative truckload transportation[J]. Transportation Research Part E： Logistics and Transportation Review， 2010，46（6）：1071-1085.
　　[11] Liu R， Jiang Z， Fung R Y K， et al. Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration[J]. Computers & Operations Research， 2010，37（5）：950-959.
　　[12] Wang X， Kopfer H. Rolling horizon planning for a dynamic collaborative routing problem with full-truckload pickup and delivery requests[J]. Flexible Services and Manufacturing Journal， 2015（5）：1-25.
　　[13] Chebbi O， Chaouachi J. Multi-objective iterated greedy variable neighborhood search algorithm for solving a full-load automated guided vehicle routing problem with battery constraints[J]. Electronic Notes in Discrete Mathematics， 2015，47：165-172.
　　[14] Bai R， Xue N， Chen J， et al. A set-covering model for a bidirectional multi-shift full truckload vehicle rout-ing problem[J]. Transportation Research Part B： Methodological， 2015，79：134-148.
　　[15] 陈新庄，郭强，范昌胜. 多车场满载车辆路径优化算法[J]. 计算机工程与设计，2008，29（22）：5866-5868.
　　[16] 范昌胜，郭强，岳爱峰. 多车场满载车辆路径问题遗传算法[J]. 陕西科技大学学报，2011，29（2）：69-74.