基于容量约束的城市共同配送路线优化

马秀丽

（湖州职业技术学院，浙江 湖州 313000）

基于容量约束的城市共同配送路线优化

马秀丽

（湖州职业技术学院，浙江 湖州 313000）

在城市共同配送中，对配送路线进行优化十分重要。介绍了CVRP模型以及城市共同配送的路线优化方法，着重分析了节约里程法的原理和计算步骤，最后通过实例，描述了不同优化方法的应用，并选出了最优的方法。

CVRP模型；城市共同配送；路线优化

1 引言

2015年8月，湖州正式成为了浙江省开展城市共同配送的两个试点城市之一。湖州市商务局在公平、公开、公正的基础上，精心挑选了6家企业分别从事不同商品的城市配送，配送的商品涉及城市快速消费品、家电、医药、酒、食品、生鲜、书报等。经过一年半的建设，湖州城市共同配送标准化建设初具规模，城市配送车辆按照《城市物流配送汽车选型技术要求》（GB/T29912）进行选择。随着“互联网+高效物流”工作的推进，客户对配送质量的要求越来越高，要在遵循湖州城市交通政策前提下，有效地将客户需要的货物送至目的地，各公司就必须开展不同形式的共同配送。在大数据、云计算、移动互联等技术日趋成熟的今天，在考虑车辆容积、了解客户分布的基础上，计算最佳配送路线是本文所要研究的问题。

2 CVRP模型

CVRP即有能力约束的车辆路径调度（Capacitated Vehicle Routing Problem，CVRP），简称“车辆路径问题”。该模型约束少，一般仅对车辆的载重和行驶的时间（或距离）有约束。

CVRP基本原理是：若干有配送需求的客户被一组配送车辆服务，这些配送车辆从物流中心出发，沿途为不同的客户送货。每辆配送车辆具有相同装载容量上限，每位客户具有特定的配送量需求,每位客户只能被一辆车服务，所有的配送车辆从物流中心出发,送完货,再回到物流中心，一辆车不能在同一个客户处停留多次，所有的配送车辆都不能超载，一条线路上所有客户的配送量之和不能超过该辆车的额定载重量。用所有配送车辆行驶的距离总和来衡量一个解的质量，且要求配送总成本最低。

CVRP的描述：设某物流中心自有k辆车，每辆配送车的最大载重量为Q，需要对n个客户(节点)进行运输配送，每辆车从物流中心出发给若干个客户送货，最终回到物流中心，客户点i的货物需求量是qi(i=1,2,…,n)，且qi〈Q。记物流中心编号为0，各客户编号为i(i=1,2,…,n)，cij表示客户i到客户j的距离。求满足车辆数最小、车辆行驶总路程最短的配送方案。

定义变量如下：

建立此问题的数学模型：

约束条件：

3 城市共同配送的线路优化方法

一般来说，城市共同配送的配送线路是指一辆配送车辆离开物流中心，按照一定顺序访问若干客户点后返回起点的行驶路线。在湖州市开展城市共同配送的过程中，各实施共同配送的物流中心以降低成本、减少污染、提高配送效率为配送路线的优化原则。因为成本与路程相关性较强，而和其他因素的相关性较小，所以选择最短路径作为目标。以路径最短作为配送路线优化目标有两种方式：

3.1 直送式配送线路优化

直送式配送又称一对一的配送，即一个物流据点对应一个客户的专线送货。在直送式配送方法下，需要一定的约束条件，也就是一个客户的需求量接近或大于可用车辆的额定重量，专门派一辆或多辆车进行一次或多次送货。这种配送方式体现的是多装快跑，选择最短配送线路，以节约时间、费用，提高配送效率，进行一对一配送，在物流配送线路图中寻找最短路径是最合适的方法，可以利用百度地图等电子地图直接找到最短路径，理论上可以用位势图、破圈法等技术。

3.2 分送式配送运输线路优化

分送式配送又称一对多的配送，即由一个物流中心对多个客户实行共同送货。这种配送方式的约束条件是同一条线路上所有客户的需求量总和不超过一辆车的额定载重量，送货时，由这一辆车装着所有客户的货物，沿着事先规划好的最优路线一一将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，减少了使用车辆数量，节省了费用，也缓解了交通紧张的压力，减少了运输对环境造成的污染。利用节约里程法确定配送路线的主要出发点是，根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来制定使配送车辆总的周转量达到或接近最小的配送方案，一般采用节约里程法路线设计技术。

在湖州城市共同配送过程中，通过考察6家物流公司的配送情况，发现一个客户的配送需求几乎没有达到车辆额定载重量的情况，并且客户分布不太集中，因此将多个客户集中起来进行整合、分拣、配货，实行共同配送，以降低送货成本。一般来说，客户的配送需求以及货品类型都是多样化的，物流中心应该按照货品类型、配送目的地对货品进行分配配送，以优化资源配置，降低运输成本。

4 节约里程法

4.1 节约里程法基本原理

图1 节约里程法原理图

如图1所示，三角定理：a+b＞c；分别配送：2a+2b；巡回配送：a+b+c；所以(2a+2b)-（a+b+c）=a+b-c＞0，由此得出，走巡回配送路线比走分别配送路线更节约里程。

4.2 节约里程法假设条件配送的是同一种或相类似的货物；各用户的位置及需求量已知；配送方有足够的运输能力；节约里程法路线要求使总的周转量最小外，还应满足所有客户的到货时间要求；不使车辆超载；每辆车每天的总运行时间及里程满足规定的要求。

4.3 节约里程法的计算步骤

利用节约里程法实现一个物流中心同时对多个客户的配送，使得配送成本最低，具体计算步骤如下：

（1）通过百度地图等电子地图找出物流中心至客户以及各客户相互间的最短线路（距离），画出最短距离矩阵。

（2）从最短距离矩阵中，计算客户相互间的节约里程，即计算a+b-c的值。

（3）将节约里程按大小顺序进行降序排序。

（4）在满足车辆额定装载量、客户需求量、送货时间限制以及客户地理位置等的条件下，按照节约里程从大到小连线，组成回路配送线路。从节约里程排序表找出产生该节约里程的两个配送点i、j，再判断连接i、j的回路是否存在合并的可能性。如果一个回路以（p，i）开始，一个回路以（j，p）结束，且满足需求量和车载量等约束条件，则该回路可以合并，并进行下面的合并操作：删除两个回路中的部分路径（i，p）和（p，j），然后引入新的连接（i，j），得到新的回路（p，…，i，j，…，p）。重复上述过程，直至没有可以合并的回路，从而得出配送优化方案。

5 节约里程法在城市共同配送中的应用

5.1 基础信息

湖州祥瑞物流中心是湖州市城市共同配送中配送货物量最大、运作最为规范的物流公司。该公司涉足家电、医药、酒、食品等商品的城乡配送业务，发展至今逐步建成了较为成熟的配送网络，覆盖了全市150多个乡镇，计划在“十三五”期间实现全市乡镇配送全覆盖。该公司在标准化建设方面领先其他5家中标的公司，经过一年多的建设，仓储和配送标准化建设基本完成。购置了50辆不同规格的标准化市内配送车辆，具体车辆信息见表1。

某日，湖州祥瑞物流中心配送部接仓储部通知，需要为7家客户配送商品，商品情况见表2，百度地图中各客户相对位置如图2所示。

表1 市内配送车辆信息及成本表

根据市场油价情况，汽油费用为6.66元/升。

表2 各客户需配送商品量

图2 各客户具体位置

客户3

5.2 配送路线优化

（1）最短距离矩阵表。通过百度电子地图，找出物流中心至客户以及客户之间的最短距离，见表3。其中P0表示祥瑞物流中心，P1为客户1，P2为客户2，以此类推。

表3 物流中心至客户以及客户之间的最短距离表

（2）节约里程表。根据表3计算各客户的节约里程，即计算a+b-c的值，得出表4。

表4 各客户的节约里程表

（3）节约里程表排序。根据节约里程表，把节约里程由大到小排序，得到表5。

表5 节约里程排序表

（4）配送路线优化方案。

①采用直送式（物流中心对客户实行一对一送货）。因为需要送货的客户有7家，每家配送量均没有超过祥瑞物流中心最小车辆的货物额定载重量（即国家标准中定义的载重量）500kg。所以采用直送式需要7辆车型Ⅰ的车，配送方案见表6。

表6 直送式配送方案

②节约里程法优化配送方案。根据公式（6）和表2，利用节约里程法得到最优路线方案见表7。

对比表6与表7，节约里程法比直送式节约里程：407km－180.9km＝226.1km，配送成本节约：395.27元－187.73元＝207.54元。优化后的配送路线图如图3所示。

图3 配送路线优化方案

6 结束语

鉴于城市共同配送货物的性质，大部分属于按重量计量的货物，采用本文的方法，确实可以为物流中心节约大量成本。随着城市共同配送中“互联网+高效物流”的推进，OTO订单日趋增多，客户也越来越分散，这就需要物流中心利用电子地图将城市划分为不同的配送区域，结合配送区域内总配送量，再考虑车辆载重量，采用节约里程算法进行配送。

[1]姜樱梅,王淑云.乳品逆向物流及其VRP模型应用[J].企业经济,2014,(2)：60-63.

[2]陈磊,霍永亮,霍波陶.基于混合遗传算法的物流车辆调度优化[J].重庆师范大学学报(自然科学版),2015,32(2)：7-12.

[3]邝海山.网购环境下城市共同配送动态车辆调度优化研究[D].重庆：重庆大学,2014.

[4]王君,李波,卢志刚.带时间窗动态车辆路径问题的优化调度策略[J].计算机工程,2012,38(13).

Optimization of Urban Joint Distribution Route Based on Capacity Constraint

Ma Xiuli
(Huzhou Vocational&Technical College,Huzhou 313000,China)

In this paper,we introduced the CVRP model and the route optimization method for urban joint distribution,then focused on the principle and calculation steps of the saving algorithm,and at the end,through a practical example,described the application of different optimization processes.

CVRP model;urban joint distribution;route optimization

F224.0；F252.14

A

1005-152X(2017)06-0137-04

10.3969/j.issn.1005-152X.2017.06.032

2017-05-09

马秀丽（1973-），女，山东汶上人，湖州职业技术学院讲师，湖州现代物流研究所研究员，硕士，研究方向：物流与供应链管理。