基于时间约束的生鲜产品配送路径优化

汤 齐，张亚丽

TANG Qi, ZHANG Ya-li

（天津工业大学 管理学院，天津 300387）

(School of Administration, Tianjin Polytechnic University, Tianjin 300387, China)

基于时间约束的生鲜产品配送路径优化

汤 齐，张亚丽

TANG Qi, ZHANG Ya-li

（天津工业大学 管理学院，天津 300387）

(School of Administration, Tianjin Polytechnic University, Tianjin 300387, China)

配送作为物流中的末端环节在保障物流效率及服务水平方面起着关键作用，其运作时间及成本直接影响物流整体的运作质量和成效。针对生鲜产品配送对车辆路径优化选择进行研究，在时间约束条件下以配送总成本最小为目标建立数学模型，经过 Matlab 编程进行求解运算，得到最优配送路径方案，通过案例来证明算法的有效性和可行性。

生鲜产品；配送路径；节约里程法；时间约束

在满足配送时效的基础上降低运作成本是物流企业追求的目标，配送路径的选择是实现该目标的关键途径之一，也是物流配送中的一个非确定性多项式难题，研究方法有禁忌搜索算法、蚁群算法、遗传算法、粒子群算法、节约里程法等[1]。这些方法在解决配送路径选择问题时，多数只考虑节约里程数、时间约束、客户满意度等影响因素，未考虑运输车辆单位成本，而运输车辆单位成本作为配送成本中重要的影响因素，对生鲜产品配送成本的影响尤为突出。因此，综合考虑运输成本、制冷成本及惩罚成本，结合时间约束建立模型，运用节约里程法对生鲜产品配送路径进行优化，对提升配送时效、降低物流配送成本有重要意义[2]。

1　基于时间约束的配送路径优化

配送是指将物资从配送中心运到一个或多个需求点的过程。假设 1 个配送中心向几个需求量不同的需求点进行物资配送，在配送活动中会有多种路线和车辆可供选择。如果配送中心事先规划不合理，在运送过程中可能会发生重复、迂回、倒流运输等现象，造成配送时间增加，配送成本提升，配送效率降低。在生鲜产品配送中，配送时间对于提高物流服务水平、降低物流成本的影响很大，因而基于时间约束对生鲜产品配送路径优化选择问题进行研究。

1.1基于 Dijkstra 算法的最短路径分析

迪杰斯特拉 (Dijkstra) 算法的基本思想是从出发点 vs开始，逐步给每个节点 vj标号为，其中 dj是出发点 vs到节点 vj的最短路径里程 (从节点到自身的最短路径的距离为零)，vi是节点 vj的前个节点。从出发点 vs到点 vj的最短路径算法步骤如下。

（1）给出发点 v1标号

（2）将所有的节点分为已标号节点和未标号节点。

（3）从已标号节点 vi到所有未标号点中选择路径最短的节点 vj，节点 vj标号中的 dj= min (di+ cik)，其中 cik为点 vi到未标号 k 节点的直接最短路线，计算 dj，对 vj进行标号。

（4）重复上述步骤，直至所有节点都标号，终点节点 vn对应的 dn为出发点 v1至节点 vn的最短路径，反向追踪可求出最短路径。

在物流配送过程中，配送中心到每个需求点及需求点之间可以选择多种路线进行运输。将配送中心作为起始点 v1，vn作为一个需求点，其余节点作为路线拐角节点，每个拐角间路线为 vi到 vj的直接最短路径，这样可以通过 Dijkstra 算法得出配送中心到各需求点的最短路径，各需求点间最短路径也可同理求出。

1.2基于时间约束的配送路径优化模型

节约里程法是解决配送中路径选择问题的启发式算法，对配送中心向需求点逐一往返配送模式进行改进，采用车辆在一定约束条件限制下，如车辆载重量限制、行驶里程数限制、交发货时间限制、发送量限制等，连续对多个需求点进行配送，达到一定的优化目标，如减少运输车辆数量、提高车辆满载率、降低人工及运输成本、缩短配送里程、节省时间等。

节约里程法根据三角形任一边之长小于其他两边之和的原理，采用将配送网络中的 2 个回路拆分合成 1 个回路的方法，依次将配送中心向多个需求点的单独配送路线合并成 1 个连续配送多个需求点的路线，当配送路线上的各需求点需求量之和达到配送车辆的最大载重上限，或者合并路线达到运输里程上限，或者配送时间达到配送中心到各需求点的时间上限时，返回需求中心[3]，继续优化下一辆车的配送路线。例如，由配送中心 P 向 2 个需求点 A 和 B 进行配送，根据 Dijkstra 算法求出配送中心到 2 个需求点的最短路径分别为 PA 和 PB，2 个需求点 A 与 B 间的最短路径为 AB，方案 1 配送中心用 2 台车辆分别对 2 个需求点各自往返配送，运输总里程为：s1= 2 (PA + PB)，其配送路线如图1a 所示。方案 2 用 1 辆车在条件允许的情况下连续送货，则运输总里程为：s2= PA + AB + BP，其配送路线如图1b 所示。比较 2 种方案，方案 2 较方案 1 节约运输里程为：Δs = PA + PB - AB[4]。

运用节约里程法对配送中心向各需求点配送生鲜产品的路径进行优化，以配送总成本最小为目标建立数学模型[5-6]为

图1　节约里程法原理

式中：CT为总的运输成本，元；CP为总的惩罚成本，元；CM为总的制冷成本，元；N 为需求点数量，个；K 为需要的车辆数，辆；ck为第 k 辆车的单位运输成本，元/h；dij为从 i 地到 j 地的距离，km；cp为单位时间延迟的惩罚成本，元/h；ti为车辆实际到达 i 地的时间，h；Ti为规定到达 i 地的时间上限，h；β 为制冷成本系数；Qk为第 k 辆车最大载货量，t；v 为车辆单位时间的速度，km/h；t 为单位物资卸车时间，h/t；qi为第 i 处的需求量，t；Q0是配送中心的总储存量，t；Sk为第 k 辆车最大行驶里程量，km；sk是第 k 辆车实际行驶里程量，km；xijk=

2　案例分析

某配送中心需要向 8 个分销点配送生鲜产品，共有 3 种冷藏车型可以选择，分别为 2 t 冷藏车 4辆、4 t 冷藏车 3 辆和 6 t 冷藏车 2 辆，3 种类型冷藏车的单位运输成本分别为 2.5 元/h、2.8 元/h和 3.0 元/h，车辆平均速度为 40 km/h，单位物资卸车时间为 0.25 h/t，制冷成本系数为 12，车辆最大行驶里程量为200 km，单位惩罚成本为 40 元/h，不足 1 h 按 1 h 计算。各分销点需求量及时间上限如表1 所示[7]。利用 Dijkstra算法求出配送中心点 P 与各分销点及各分销点之间最短距离如表2 所示。

表1　各分销点需求量及时间上限列表

表2　配送中心点 P 与各分销点及各分销点之间的最短距离列表km

根据模型 ⑴，经过 Matlab 编程进行总成本最小的最优车辆路径选择求解运算，可以得到最优配送路径方案如表3 所示[8]。

表3　最优配送方案表

优化后的配送路径方案与配送中心向需求点逐一往返配送方案结果比较如表4 所示。

表4　优化前后路径选择成本比较分析 　　元

从表4 中可以看出优化后的方案成本更小，选择合适的车辆给合适的客户经过合适的路线进行配送，可以有效降低配送成本。模型 ⑴ 中没有考虑车辆购买、损耗和员工工资等影响因素，案例中配送中心向需求点逐一往返配送方案用 8 辆车 8 个司机，而优化后用 4 辆车 4 个司机，如果考虑车辆购买、损耗和员工工资等影响因素，可以更好的比较出配送路径优化后的优势。

3　结束语

在配送中选择合理的路线与车辆对节约配送成本具有很大影响，基于时间约束的配送路径优化模型能够为配送车路径选择问题提供可以借鉴的理论指导和依据。模型 ⑴ 考虑了生鲜配送中的主要影响因素，在实际问题中，可以根据自身配送特点结合其他重要因素进行运用，在尽量满足客户要求的条件下，优化选择配送路径，减少配送车辆数和人工投入，降低配送成本，提高车辆利用率及配送中心的工作效率。

[1] 李 松，刘 兴，李瑞彩. 基于混合禁忌搜索算法的物流配送路径优化问题研究[J]. 铁道运输与经济，2007，29(3)：66-69. LI Song，LIU Xing，LI Rui-cai. Study on Optimization of Logistics Distribution Route based on Mixed Tabu Search Algorithm[J]. Railway Transport and Economy，2007，29(3)：66-69.

[2] 姚卓顺. 带时间窗的连锁超市生鲜品配送车辆路径优化[J].商业时代，2014(29)：28-29. YAO Zhuo-shun. Optimization Design of the Delivery Vehicle Route by Supermarket Chains with Time Windows[J]. Journal of Commercial Times，2014 (29)：28-29.

[3] 张文华. 基于节约里程法的物流配送路线优化[J]. 物流工程与管理，2012，34(3)：143-144，146. ZHANG Wen-hua. Route Optimization of Logistics Distribution based on Saving Algorithm[J]. Logistics Engineering and Management，2012，34(3)：143-144，146.

[4] 于 航，张 凯. 基于节约里程法的鲜活农产品物流配送车辆路线的最优设计[J]. 安徽农业科学，2011，39(28)：17701-17703. YU Hang，ZHANG Kai. Optimal Design of Fresh Produce Logistics Vehicle Route based on the Method of Mileage Saving Method[J]. Journal of Anhui Agricultural Sciences，2011，39(28)：17701-17703.

[5] 郑 静，程幼明. 基于时间约束的节约里程法配送路径优化研究[J]. 物流工程与管理，2010，32(10)：89-90. ZHENG Jing，CHENG You-ming. Optimization Design of the Delivery Route by Vehicles Scheduling Program with Time Windows[J]. Logistics Engineering and Management，2010，32(10)：89-90.

[6] 邵举平. 生鲜农产品配送中带时窗的 VRP 模型与算法[J]. 工业工程与管理，2015，20(1)：122-127，134. SHAO Ju-ping. Research on Multi-objective Optimization for Fresh Agricultural Products VRP Problem[J]. Industrial Engineering and Management，2015，20(1)：122-127，134.

[7] 李 军. 有时间窗的车辆路线安排问题的启发式算法[J]. 系统工程，1996，14(5)：45-50. LI Jun. A Heuristic Algorithm for Vehicle Routing Scheduling Problem with Time Windows[J]. Systems Engineering，1996，14(5)：45-50.

[8] 刘俊娥，李 奇. 基于节约里程法的北京市家乐福超市配送线路优化方案[J]. 物流技术，2015，34(1)：107-109. LIU Jun-e，LI Qi. Study on Distribution Route Optimization Plan of Beijing Carrefour Supermarket based on Saving Algorithm[J]. Journal of Logistics Technology，2015，34(1)：107-109.

责任编辑：王 静

Route Optimization of Fresh Product Delivery based on Time Constraints

Delivery, as the last link of logistics, has the key roles on ensuring logistic efficiency and service level, and its operation time and cost have direct influence on overall operation quality and effects of logistics. Targeting with the optimized selection of vehicle routes of fresh product delivery was studied, the mathematical model was established under time constraints by taking minimization of total delivery cost as the object, optimized program of delivery route was achieved by means of matlab programming, and the validity and feasibility of the calculation method was proved by example.

Fresh Product; Delivery Route; Saving Algorithm; Time Constraints

1003-1421(2016)06-0040-04

U295

B

10.16668/j.cnki.issn.1003-1421.2016.06.08

2015-12-25

天津市教委社会科学重大项目 (2014ZD34)