﻿ 改进AHP-GA算法的多目标配送路径优化
 计算机系统应用  2019, Vol. 28 Issue (2): 152-157 PDF

Multi-Objective Location Routing Optimization of Improved AHP-GA
LI Feng-Kun
School of Intelligence and Electronic Engineering, Dalian Neusoft University of Information, Dalian 116023, China
Foundation item: Natural Science Foundation of Liaoning Province (20170520398); Scientific Research Program of Education Bureau, Liaoning Province (L2015041, L2012492)
Abstract: In order to optimize the delivery path of express delivery, a mathematical model based on time window is given. In this study, improved AHP-GA algorithm is used to optimize multi-target vehicle routing, and median Analytic Hierarchy Process (AHP) is used to compare the weight coefficients of multiple sub-targets, and it is not susceptible to extremes. Thus, the multi-objective optimization problem is transformed into a single objective optimization problem. The simple natural numbers are used to code the vehicle path to avoid duplication of the paths. The customer’s requirement for arrival time window, including the opportunity cost of the vehicle to arrive before the agreed time, and the cost of the fine after the agreed time. Finally, this study takes 1 distribution center and 20 service customers for example, the mathematical model constructed in this study is optimized by using traditional GA algorithm and using improved AHP-GA algorithm respectively. The simulation results show that the optimal solution can be obtained efficiently by using improved AHP-GA algorithm in multi-objective distribution path optimization problem.
Key words: improved AHP-GA algorithm     multi-objective distribution path     time-window

1 引言

2 问题描述

(1)配送中心的配送车辆的数量、型号一定;

(2)每一辆配送车的负载量必须大于等于所行驶路线上所有待服务客户需求货物的总重量, 配送车不得超载运行;

(3)每一辆配送车的配送时间有预定上限, 不得超时间运行;

(4)配送中心为多个, 并且每次仅由一个配送中心为某条路径上的客户配送货物, 并最终回到出发的配送中心.

(5)每一个客户存在且仅存在于一条配送路线上.

(6)满足客户要求的时间窗. 如果准时或提前将货物配送给顾客, 则不予惩罚; 否则, 要给予惩罚.

3 数学模型构建

 $\min{P_1} = \sum \limits_i \sum \limits_j \sum \limits_k {c_{ij}}{x_{ijk}}$ (1)
 $\min {P_2} = {m_1}\sum \limits_{i = 1}^n + {m_2}\sum \limits_{i = 1}^n \max \left( {{t_i} - L{T_i}, 0} \right)$ (2)
 $\min{P_3} = \sum \limits_{k = 1}^K \sum \limits_{j = 0}^N {x_{0jk}}$ (3)
 ${\rm{s.t.}}\left\{\begin{array}{l} \displaystyle\sum \limits_i {g_i}{y_{ki}} \le q, \;\;\forall k\\ \displaystyle\sum \limits_k {y_{ki}} = 1, \;\;i = 1, \cdots , n\\ \displaystyle\sum \limits_k {x_{ijk}} = {y_{kj}},\;\;j = 1, \cdots , n \;\;\forall k\\ \displaystyle\sum \limits_k {x_{ijk}} = {y_{ki}},\;\;i = 1, \cdots , n \;\;\forall k \end{array}\right.$

${x_{ijk}} = \left\{ {\begin{array}{*{20}{c}} 0, \\ 1, \end{array}} \right.\;\; i, j = 0, 1, \cdots n;\forall k$ , 其中, ${x_{ijk}}$ 表示车辆k, 由i离开, 开往j.

${{{y}}_{{{ki}}}} = \left\{ {\begin{array}{*{20}{c}} 0, \\ 1, \end{array}} \right.\;\; {{i}} = 0, 1, \cdots {{n}};\forall k$ , 其中, ${y_{ki}}$ 表示由车辆k来完成客户i的需求.

${c_{ij}}$ 表示从点i到点j的费用; $[E{T_i}, L{T_i}]$ 表示该任务执行所允许的时间范围, ${m_1}$ 表示在 $E{T_i}$ 之前到达任务点等待的单位时间成本, ${m_2}$ 表示在 $L{T_i}$ 之后到达点i, 所交的罚金成本. 目标函数(1)表示运输成本, (2)表示时间惩罚与机会成本, (3)表示车辆数目最少. 将目标函数进行归一化处理, 使其取值范围在[0, 1]之间.

 ${P_1}' = \frac{{{P_1} - {P_1}_{\min}}}{{{P_1}_{\max} - {P_1}_{\min}}}$ (4)
 ${P_2}' = \frac{{{P_2} - {P_2}_{\min}}}{{{P_2}_{\max} - {P_2}_{\min}}}$ (5)
 ${P_3}' = \frac{{{P_3} - {P_3}_{\min}}}{{{P_3}_{\max} - {P_3}_{\min}}}$ (6)
 $f\left( {{P_1}', {P_2}', {P_3}'} \right) = {w_1}{P_1}' + {w_2}{P_2}' + {w_3}{P_3}'$ (7)

4 构建评价指标权重子集

(1)分析模型, 建立递阶层次结构, 如图1所示.

(2)根据专家打分, 对准则层进行指标重要性排序.

(3)中位数是指在变量数列按照有序(升序或者降序)排列的时候, 位于中间位置所对应的变量值[3]. 故中位数不受分布数列的极大值和极小值的影响, 从而在一定程度上提高了中位数对分布数列的代表性. 因为中位数不易受极端值影响且与所有评价值距离最短的优点[9], 故采用中位数确定指标权重, 通过归一化处理使得所有指标的中位数权重之和等于1.

 图 1 快递配送方案层次结构(AHP)图

P1S1: (0.117, 0.542, 0.232, 0.312, 0.810);

P1S2: (0.223, 0.479, 0.978, 0.202, 0.526);

P2S2: (0.187, 0.189, 0.002, 0.098, 0.198);

P2S3: (0.141, 0.132, 0.147, 0.201, 0.151);

P3: (0.478, 0.232, 0.131, 0.125, 0.007).

 $\left( {0.312, 0.223, 0.187, 0.147, 0.131} \right)$

(4)计算各层要素对系统目的(总目标的合成(总)权重, 选择最优方案. 由(3)可得因素层指标项所占整个指标体系的权重.

 \begin{aligned} ({w_{P_1S_1,}}{w_{P_1S_2}},{w_{P_2S_2}},&{w_{P_2S_3,}}{w_{P_3}}) = \\ &{\left( {0.312,0.223,0.187,0.147,0.131} \right)^{\rm{T}}} \end{aligned} (8)

5 改进遗传算法求解 5.1 编码设计

 图 2 编码设计

5.2 选择操作

5.3 交叉操作

 图 3 交叉操作

 ${p_{ci}} = \left\{ {\begin{array}{*{20}{l}} {{p_{c\max}} \!-\!\! ({p_{c\max}} \!-\! {p_{c\min}})\left( {\displaystyle\frac{g}{{2G}} \!+\! \displaystyle\frac{{{f_i} \!-\! \bar f}}{{2\left( {{f_{\max}} \!-\! \bar f} \right)}}} \right), {f_i} \ge \bar f}\\ {{p_{c\max}},{f_i} < \bar f} \end{array}} \right.$ (9)
 ${p_{c\max}} = \left\{ {\begin{array}{*{20}{l}} {0.9, g \leqslant G/4} \\ {0.8, G/4 < g \leqslant 3G/4} \\ {0.7, \displaystyle\frac{{3G}}{4} < g \leqslant G} \end{array}} \right.$ (10)

5.4 变异操作

5.5 适应度评估

 图 4 变异操作

6 实例分析 6.1 实例介绍

GA算法与改进AHP-GA算法选取的种群数目均为50, 进化代数为50, 种群的交叉概率参照公式(9)和公式(10), 故交叉概率初始值为0.9 , 种群变异概率为0.1, 选择同型号车辆, 设置车辆数目为3, 车辆载重量为1 t, 设置平均车速为60 km/h. 罚金成本系数 ${m_2} = 10.00$ .

6.2 实验结果

 图 5 GA算法优化调度成本结果

 图 6 改进AHP-GA算法优化调度成本结果

 图 7 改进AHP-GA快递配送路径结果图

7 结论

 [1] 蒋国清, 潘勇, 胡飞跃. 两阶段式的物流配送路径优化方法. 计算机工程与应用, 2015, 51(2): 255-258, 264. DOI:10.3778/j.issn.1002-8331.1404-0342 [2] 巩固, 胡晓婷, 卫开夏, 等. 物流配送车辆路径问题的优化研究. 计算机工程与科学, 2011, 33(5): 106-111. DOI:10.3969/j.issn.1007-130X.2011.05.021 [3] 何文胜, 陈武, 陈尘. 中位数计算公式及数学性质的新认识. 统计与决策, 2018(9): 74-76. [4] Hiermann G, Puchinger J, Ropke S, et al. The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 2016, 252(3): 995-1018. DOI:10.1016/j.ejor.2016.01.038 [5] 张立毅, 王迎, 费腾, 等. 混沌扰动模拟退火蚁群算法低碳物流路径优化. 计算机工程与应用, 2017, 53(1): 63-68, 102. DOI:10.3778/j.issn.1002-8331.1503-0167 [6] 戚远航, 蔡延光, 蔡颢, 等. 带时间窗的车辆路径问题的离散蝙蝠算法. 电子学报, 2018, 46(3): 672-679. DOI:10.3969/j.issn.0372-2112.2018.03.024 [7] 刘恒宇, 汝宜红. 考虑交通拥堵及工作量平衡性的一致性车辆路径问题. 西南交通大学学报, 2016, 51(5): 931-937. DOI:10.3969/j.issn.0258-2724.2016.05.016 [8] 杨志清. 城市快递配送条件下的多目标车辆路径优化研究[硕士学位论文]. 哈尔滨: 哈尔滨工业大学, 2015. [9] 王凌峰, 姚依楠. 主观线性加权评价问题的新方法: 中位数层次分析法. 系统科学学报, 2018, 26(1): 96-99. [10] 于莹莹, 陈燕, 李桃迎. 改进的遗传算法求解旅行商问题. 控制与决策, 2014, 29(8): 1483-1488.