﻿ 动态物流中多源多点最佳路径算法研究
 计算机系统应用  2019, Vol. 28 Issue (2): 253-258 PDF

Research on Multi-Source and Multi-Point Optimal Path Algorithm in Dynamic Logistics
BI Ming-Hua, HE Li-Li
School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China
Foundation item: Major Program of Science and Technology Bureau, Zhejiang Province (2015C03001)
Abstract: In the multi-source and multi-point environment, the path optimization involving dynamic loading and product distribution in dynamic logistics is a very complicated problem. Aiming at the diversification of goods demand in the actual distribution process and the path optimization problem of multi-vehicle delivery and high idling rate, this study proposes a new scheduling and distribution method. By establishing a vehicle loading and distribution path model, using the multi-source point multi-destination, weight correction, path optimization, etc. as constraints, a new way of simulating cell division is used to generate the next generation and improved the existing genetic algorithm to solve the problem. This method optimizes the generation of the initial population can quickly obtain the global optimal solution, jump out of the genetic premature convergence, get the best path, reduce the distribution cost and improve the distribution efficiency.
Key words: multiple points and multiple sources     weight correction     path planning     genetic algorithm

1 问题完整性描述

 图 1 配送方式图

2 将实际问题转化为数学模型

 $\begin{split} minF = &\sum\limits_{{\rm{i = 1}}}^{N - 1} {dis(i,i + 1)} \\ &+\sum\limits_{j = 1}^{J - 1} {(C \times \sum\limits_{k \in K,\atop {m \in K,\atop k \ne m}} {dis({{\rm{j}}_k},{{(j + 1)}_m})} + C' \times dis(j,j + 1))} \end{split}$ (1)

1) 存在多个仓库 ${j_1},{j_2},{j_3}, \cdots, {j_n}$ , 其存储的产品种类分别为 ${{{h}}_1},{h_2},{h_3}, \cdots, {h_n}$ .

2) 各个需求点对不同种产品的需求总和不超过其存储总量:

 $\sum\limits_{i = 1}^n {{b_m}(i) \leqslant Q({b_m})} \;\;\; m \in \{ 1,2,3, \cdots ,n\}$ (2)

3) 车辆的装载重量不超过该车型的最大载重量

 $\sum\limits_{{\rm{j}} = 1}^{J - 1} {(q(j) - \sum\limits_{i = 1}^I {q(i) + q(j + 1)) < Q} }$ (3)

4) 仓库只经过一次.

 $\sum {{c_j} = 1}$ (4)

${c_j}$ 表示仓库经过的次数. 源于贪心策略和现实运输情况, 这里规定仓库只经过一次, 即将所有需求点对此仓库存储的货物需求总量一次性装车, 减少其配送成本.

5) 每个需求点经过次数最少一次且不能超过两次.

 $1 \leqslant \sum {{c_{\rm{i}}} \leqslant 2}$ (5)

${c_{\rm{i}}}$ 表示需求点经过的次数. 需求点每多经过一次, 其成本多增加一份, 因此这里规定需求点最少经过一次且不能超过2次, 若需求总量大于车辆本身载重且此需求点适应度值较高, 允许经过一次部分卸货以减少需求点的总量, 之后第二次经过时满足剩余需求. 否则, 只允许经过一次且满足此需求点所有种类的货物需求.

3 对模型求解 3.1 编码方式

 图 2 染色体编码

3.2 初始种群的产生

1) 首先, 计算出所有目的地的需求总量与汽车载重量之间的差值C.

2) 将染色体编码表示为数组chromosome, chromosome中的下标为0的位置为0, 表示从某一仓库出发.

3) 使用Random函数生成随机数, 用来检测下一个到达的点是否为仓库点. 其概率为: 仓库点数/(需求点数+仓库点数), 当小于此值时, 即为仓库点.

4) 当判定为仓库点时, 若为最后一个仓库点且差值C大于0, 转步骤3)若为最后一个仓库点且差值C不大于0, 则说明汽车载重量已经满足, 执行步骤5); 若非最后一个仓库点且差值C不大于 0, 则将剩余仓库点依次加入数组chromosome并执行步骤5); 若非最后一个仓库点且差值C大于0, 判定此随机数是否已经加入过数组chromosome, 即: 是否此需求点已经经过一次, 若此随机数未加入过数组chromosome, 则取反加入并计算每个需求点对此仓库货物的需求量的和 $\sum\limits_{{\rm{i}} = 1}^N {{{{P}}_{{i}}}({h_j})}$ , 将其加入差值C. 若已加入, 则判断相邻数是否加入, 直到找到未加入的仓库点, 并取反加入数组chromosome. 当判定不为仓库时, 则重新生成随机数为下一次到达的需求点. 若此需求点已经加入数组chromosome, 处理方式与仓库相同, 并将差值C的值减去此需求点需求的值. 完成后执行步骤3)继续查找下一次需要经过的仓库点或需求点.

5) 到此阶段说明当前的差值C已经不大于0, 后续只需要在各个需求点之间寻找一条最优路径即可.

 图 3 产生初始种群的流程图

3.3 适应度函数的确定

1) 当车辆由仓库到达第一个需求点时的适应度函数如下:

 ${{N}}({s_j},{h_j}) = \frac{{M \cdot {P_n}({h_j})}}{{K \cdot dis({s_j},{p_n})}}$ (6)

2) 当车辆离开第一个需求点转至下一个需求点(或仓库)时适应度函数如下:

 {{N}}({p_i},{p_n}) = \left\{ {\begin{aligned} & {\frac{{M \cdot {P_n}({h_j})}}{{K \cdot dis({p_i},{p_n})}} \times \frac{1}{{C - {P_n}({h_j})}},{P_n}({h_j}) < C}\\ & {\frac{{M \cdot {P_n}({h_j})}}{{K \cdot dis({p_i},{p_n})}} \times {{T,}}\;\;\;\;\;\;\;\;\;\;\;\;{P_n}({h_j}) \ge C} \end{aligned}} \right. (7)

3.4 选择算子

3.5 模拟细胞分裂

1) 若只有两个仓库点, 则随机选择两个仓库点之间的任意一个需求点, 判定其到其他需求点的适应度值, 找到适应值最大的需求点, 将其与该需求点之后的第一个需求点交换. 判定交换后的总适应度值与交换之前的总适应度值大小, 若小于交换之前的总适应度值, 则舍弃此次基因重组. 否则, 则标记该需求点, 下次重组时若随机到该需求点, 则计算之后的需求点.

2) 若仓库点数大于2, 则每个仓库点之间重复步骤1).

3) 对于最后一个仓库点之后的所有需求点, 采用步骤1)的方式判定其重组后的位置.

3.6 选择变异方式

3.7 结束标识

4 实验分析

 图 4 10次测试生成的最短路程(单位: KM)

 图 5 需求总量与汽车载重的差值随经过城市数的变化图

5 结论

 [1] 焦李成, 刘静, 钟伟才. 协同进化计算与多智能体系统. 北京: 科学出版社, 2006. [2] 王小平, 曹立明. 遗传算法——理论, 应用与软件实现.西安: 西安交通大学出版社, 1998. [3] 孙刘诚, 孙焰. 带订单选择车辆路径问题的模型与算法. 交通运输系统工程与信息, 2018, 18(2): 194-200. [4] 涂伟, 李清泉, 方志祥. 基于网络Voronoi图的大规模多仓库物流配送路径优化. 测绘学报, 2014, 43(10): 1075-1082. [5] Zhao ZY, Zhan YR. A cost analysis method on location planning for logistics distribution network system. Proceedings of the 16th International Conference on Industrial Engineering and Engineering Management. Beijing, China. 2009. 395–399. [6] 丁蓓, 魏振春, 孙仁浩. 基于遗传算法的最小成本配送策略研究. 合肥工业大学学报(自然科学版), 2018, 41(2): 273-278. DOI:10.3969/j.issn.1003-5060.2018.02.025 [7] 范文兵, 冯文. 混合遗传算法的带时间窗卷烟物流车辆路径优化. 现代电子技术, 2018, 41(11): 119-123, 128. [8] Nazif H, Lee LS. Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 2012, 36(5): 2110-2117. DOI:10.1016/j.apm.2011.08.010 [9] 袁麟博, 章卫国, 李广文. 一种基于遗传算法－模式搜索法的无人机路径规划. 弹箭与制导学报, 2009, 29(3): 279-282. DOI:10.3969/j.issn.1673-9728.2009.03.082 [10] 邝航宇, 金晶, 苏勇. 自适应遗传算法交叉变异算子的改进. 计算机工程与应用, 2006, 42(12): 93-96, 99. DOI:10.3321/j.issn:1002-8331.2006.12.028 [11] 卢月品, 赵阳, 孟跃强, 等. 基于改进遗传算法的狭窄空间路径规划. 计算机应用研究, 2015, 32(2): 413-418. DOI:10.3969/j.issn.1001-3695.2015.02.021 [12] 雷伟军, 程筱胜, 戴宁, 等. 基于改进遗传算法的多模型加工路径规划. 机械工程学报, 2014, 50(11): 153-161. [13] 庄健, 杨清宇, 杜海峰, 等. 一种高效的复杂系统遗传算法. 软件学报, 2010, 21(11): 2790-2801. [14] 王振锋, 王旭, 葛显龙. 基于遗传算法的不同约束条件车辆调度问题研究. 计算机应用研究, 2010, 27(10): 3673-3675. [15] Montemanni R, Gambardella LM, Rizzoli AE, et al. Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization, 2005, 10(4): 327-343. DOI:10.1007/s10878-005-4922-6