闫会姝

基于集送货需求的车辆路径优化问题研究

闫会姝

车辆在服务过程中，既可能面对集货需求，也可能面对送货需求。在国内外学者研究的基础上，提出一种新的解决VRPSDP问题的方法。在系统分析同时具有集送货需求的物流网络机构与要素的基础上，构建基于集送货需求的车辆路径优化模型，利用lingo软件进行优化求解。实例仿真结果表明，通过该模型的建立及软件的应用，能够对车辆的路径进行优化，能够有效地减少车辆的运输成本，提高物流运作的效率。

集送货需求；路径优化；实例仿真；lingo软件

随着人们的环保意识逐渐加强，各企业根据自身可持续发展的需要，原材料、半成品、制成品、废旧品的回收和再利用越来越受到关注，逆向物流的问题得到了越来越多学者的关注。在逆向物流运作过程中涉及很多复杂的规划问题，逆向物流的车辆路径优化就是其中之一，由此延伸出很多不同类型的VRP［1］，如VRPB（Vehicle Routing Problem with Backhauls）、VRPBM（Vehicle Routing Problem with Backhauls of Mixed Loads）等［2］。在实际的生活中，顾客可能会有配送和回收的需求，如饮料供应商在给零售商店送饮料的同时，店主可能会要求厂家回收空瓶子。由于将送货和回收单独进行会增加成本，因此将正向物流和逆向物流同时加以考虑成为解决问题的有效途径。该问题是经典VRP问题的一个拓展，是带有同时取货和送货功能的车辆路径优化问题（Vehicle Routing Problem with Simultaneous Delivery and pickup，VRPDP）。

一、集送货需求车辆路径的优化问题概述

（一）研究现状

目前，各界学者将集送货需求的逆向物流车辆路径优化问题［3］分为三类：第一类是Anily、Toth和Vigo、Brandao等，研究的主题是带回程载货的车辆路径问题（VRPB），这类问题适用于每个客户要求服务的内容不一样，有的是对货物的需求，有的是要将货物运到仓库。通过将该问题分成先送货再集货两个阶段，只有将所有的需求点送完后才对集货客户服务。第二类是Casco、Salhi和Nagy［4］等，研究的主题是混合集送货需求的车辆路径问题（VRPMPD）。这类问题在需求方面假设与第一个问题一致，但是放宽了配送的约束条件，不再要求配货必须在集货前，可以混合进行。第三类问题是同时具有集送货需求的车辆路径优化问题（VRPSDP）。对于VRPSDP的求解通常采用启发式算法和元启发式算法，同时遗传算法、蚁群算法、模拟退火算法［4］都有研究，但是对于求解质量还有待进一步改进（见图1）。

图1 集送货车辆路线问题分类

（二）本文研究的数据来源及创新点

笔者以重庆一家集啤酒生产和啤酒瓶回收一体的公司为背景，数据来源于图书馆、互联网和文献资料等多种途径。笔者首先分析专家学者关于集送货车辆路径优化问题的研究思路和研究方法，然后提出基于集送货需求的车辆路径优化问题研究的基本假设，定义参数、变量和确定目标函数，建立VRPDP车辆路径优化问题的模型。笔者主要是采用lingo软件，以满足相应的约束条件为前提，最终实现运输成本最小化的目标。创新点在于对模型的建立，同时考虑了运输距离变动成本、启动车辆数量成本及总的车辆货损成本，对于提高企业的物流运作效率具有重要的现实意义［5］。

二、VRPSDP车辆路径优化问题的模型构建

VRPSDP（Vehicle Routing Problem with Simultaneous Delivery and Pickup）是VRP问题的延伸，可以描述为：有一个配送中心或者仓库，有K辆相同型号，相同最大载重量的货车从起始站点出发，服务于沿途的各个客户点；这些客户点包括只有需求，只有供给，既有需求又有供给三种情况，各类客户被服务完成后车辆最终返回到配送中心。车辆在运输过程中，需要满足每辆车的实际载重量不大于车辆的最大载重量，每个服务点有接近被赋予一次的约束条件，最终求出车辆的行车路线使得总的行驶路程最低的方案，实现总的运输效率最高和总的消耗成本最少的目标。

（一）基本假设

（1）客户的位置、需求量和时间窗在集送货过程中完全已知，且车辆的最大装载量应小于单个客户点的需求量、货物回收量。

（2）在仓储中心的货物数量充足，货物的配送过程中不会出现缺货的现象。

（3）集送货过程中货物只考虑重量的约束，不考虑体积、形状的限制。

2）调研阶段：在设计前期，没有进行现场调研，仅根据地形图确认管线位置，施工单位进入现场开挖后，发现设计与现场情况不符，需要重新调整设计，在一定程度上影响了施工进度。

（4）在任何时候车辆的最大载重量应大于所装载的货物量。

（5）每辆车辆均以仓库作为出发点，对各客户点服务完成后重新返回到仓库。

（6）服务车辆的行驶速度在集送货过程中为恒定值，不考虑其他物理因素，不考虑交通堵塞等现象［6］。

（7）每个客户只能被一辆车进行服务一次。

（二）参数和变量的定义

假设配送中心最多可以用k辆车（k=1，2，…，K）对L个客户（i=1，2，…，l）进行服务。

M代表节点集合。

N代表客户点集合。N={i}，i=0表示配送中心，i= 1，2，…，n为客户节点。

α代表单位运输距离的运输成本。

β代表单位车辆的启用成本。

T代表车辆的最大载重能力。

C代表客户点i与客户点j之间的距离。

di代表客户点i的送货需求。

pi代表客户点i的取货需求。

（三）模型构建

车辆路径优化的目标是在满足所有客户集送货需求及车辆负载能力等约束条件下找出运输成本最低的行驶路线。成本包括运输距离变动成本、启动车辆数量成本及货损成本。之前大量学者的研究只考虑了运输距离的变动成本，笔者在建模过程中将考虑运输距离变动成本、启动车辆数量成本及货损成本，建立改进的VRPSDP模型［6］。

目标函数：

约束条件：

三、算例仿真

重庆某企业是一家集啤酒生产和啤酒瓶回收为一体的公司，公司会定期派车辆对啤酒的销售商进行送货并且根据销售商的需求将啤酒瓶回收。笔者主要以该公司在重庆主城的集送货群为研究对象，将主要的6个销售商点通过Google地图进行投影，各销售点到配送中心的距离及销售点之间的距离见表1，销售点对啤酒的需求量以及啤酒瓶的取货量见表2。假定所使用的货车的最大容量为240，固定使用成本为80。为了软件计算方便，将销售商编号从小到大设置成X1—X6，配送中心设为X0。Xij表示连接ij这两个供应商的那条路，节点分别代表配送中心，石桥铺销售点，渝北销售点，南岸销售点，璧山销售点，九龙坡销售点，北碚销售点。

表1 配送中心与客户间的距离/km

使用Lingo软件在MS Windows XP、Pentium 43.06GHz、1.00GB内存的环境下对上述模型进行求解。计算结果是为了完成所有顾客的集送货需求，需要使用三条循环去获得路线。其中，路线一为X0-X1-X3-X4；路线二为X0-X2-X5-X0；路线三为X0-X6-X0。三条路线总的路程为262 km，达到局部最优。该模型是解决整数非线性规划的模型。Lingo软件能在较短的时间内取得局部最优解。

表2 车辆的送货量和取货

四、结语

本文通过构建基于集送货需求的车辆路径优化问题模型对车辆路径进行优化，同时运用lingo软件对该模型进行了优化计算与算例仿真，进一步证实了车辆路径优化对于提高物流企业的运营效率，降低物流企业的运营成本，具有重要的实践意义。

[1]马祖军.产品回收逆向物流网络优化设计模型[J].管理工程学报，2005（4）.

[2]Christian S.Efficient Local Search on the GPU：Investigations on the Vehicle Routing Problem[J].Journal of Parallel and Distributed Computing，2013（7）.

[3]Melián-Batista B，Santiago A，AngelBello F，et al.A Biobjective Vehicle Routing Problem with Time Windows：A Real Case in Tenerife[J].Applied Soft Computing Journal，2014（17）.

[4]吴斌，蔡红，樊树海，蒋南云.双倍体差分进化粒子群算法在VRPSDP中的应用研究[J].系统工程理论与实践，2010（3）.

[5]殷佳林，蒋泰.具有同时送货和取货需求的车辆路径问题的蚁群禁忌混合优化算法[J].广西科学院学报，2008（4）.

[6]王科峰，叶春明，李永林.同时送取货车辆路径问题算法研究综述[J].计算机应用研究，2013（2）.

[7]陈久梅，曾波.两级定位—路径问题的路径重连变邻域搜索人工蜂群算法[J].计算机集成制造系统，2014（5）.

（编辑：唐龙）

F252.81

A

1673-1999（2015）05-0045-03

闫会姝（1992—），女，重庆工商大学（重庆南岸400067）商务策划学院2014级硕士研究生，研究方向为物流与供应链管理。

2015-04-04

电子商务及供应链系统重庆市重点实验室开放基金项目（2013ECSC0101）。