联合配送外包策略的定位运输问题

靳文舟; 朱子轩; 巫威眺; 李婷

doi:10.13471/j.cnki.acta.snus.2019.03.30.2019B031

欢迎访问《中山大学学报(自然科学版)(中英文)》！ English Version 维普资讯中国知网万方数据

您当前的位置：

首页 >

文章列表页 >

联合配送外包策略的定位运输问题

研究论文 | 更新时间：2023-11-01

- 联合配送外包策略的定位运输问题
- Location routing problem with outsourcing strategy
- 角色： First author , 第一作者 ,
  
  机构：
  华南理工大学土木与交通学院，广东广州 510640
  
  邮箱： ctwzhjin@scut.edu.cn
  
  简介：靳文舟（1960年生），男；研究方向：交通运输规划与管理；E-mail：ctwzhjin@scut.edu.cn
  
  暂无本作者相关信息
  靳文舟
  ，
  角色：
  
  机构：
  华南理工大学土木与交通学院，广东广州 510640
  
  邮箱：
  
  暂无本作者相关信息
  朱子轩
  ，
  角色： Corresponding author , 通讯作者 ,
  
  机构：
  华南理工大学土木与交通学院，广东广州 510640
  
  邮箱： ctwtwu@scut.edu.cn
  
  简介：巫威眺（1987年生），男；研究方向：交通运输规划与管理；E-mail：ctwtwu@scut.edu.cn
  
  暂无本作者相关信息
  巫威眺
  ，
  角色：
  
  机构：
  华南理工大学土木与交通学院，广东广州 510640
  
  邮箱：
  
  暂无本作者相关信息
  李婷
  ，
- 中山大学学报(自然科学版) 2020年59卷第4期页码：89-97
- 作者机构：
  
  华南理工大学土木与交通学院，广东广州 510640
- 作者简介：
  
  靳文舟（1960年生），男；研究方向：交通运输规划与管理；E-mail：ctwzhjin@scut.edu.cn
  巫威眺（1987年生），男；研究方向：交通运输规划与管理；E-mail：ctwtwu@scut.edu.cn
- 基金信息：
  
  国家自然科学基金(61473122);国家自然科学基金(61703165);中国博士后科学基金(2016M600653);华南理工大学中央高校基本科研业务经费专项资金(D2171990)
- DOI：10.13471/j.cnki.acta.snus.2019.03.30.2019B031
  中图分类号： U491
- 纸质出版日期：2020-07-20，
  
  收稿日期：2019-03-30，
扫描看全文
引用本文

阅读全文PDF
靳文舟,朱子轩,巫威眺等.联合配送外包策略的定位运输问题[J].中山大学学报(自然科学版),2020,59(04):89-97.

JIN Wenzhou,ZHU Zixuan,WU Weitiao,et al.Location routing problem with outsourcing strategy[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2020,59(04):89-97.
靳文舟,朱子轩,巫威眺等.联合配送外包策略的定位运输问题[J].中山大学学报(自然科学版),2020,59(04):89-97. DOI： 10.13471/j.cnki.acta.snus.2019.03.30.2019B031.

JIN Wenzhou,ZHU Zixuan,WU Weitiao,et al.Location routing problem with outsourcing strategy[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2020,59(04):89-97. DOI： 10.13471/j.cnki.acta.snus.2019.03.30.2019B031.

摘要

文章提出联合外包策略的定位运输规划模型，以期通过部分车辆任务外包减少物流系统成本。考虑实际运营中的时间窗等限制条件，以及自送和外包运输成本构成，通过联合优化配送中心选址和车辆路径决策，构建了最小化物流网络总成本的模型，包括自营车辆固定成本和可变运输成本、配送中心建设的固定成本，以及外包配送的运输成本。根据问题的特征设计了遗传算法的分段编码方法。通过仿真算例，将所提出的策略与传统全部自送和全部外包运营模式进行比较。结果表明，通过部分车辆任务外包可以有效减少自送的额外成本和配送中心建设成本，从而降低系统成本，在该仿真算例中该策略较完全自送模式成本降低了8.08%，较完全外包模式成本降低了25.03%，最后通过敏感性分析考察了不同外包价格对系统决策的影响。

译

Abstract

The rapid development of logistics outsourcing has brought new opportunities for the supply chain integration design. This paper proposes a location routing problem planning model with the outsourcing strategy, with the objective to reduce the logistics system cost via partially outsourcing vehicle tasks. Considering the constraints in actual operation such as time windows, and the composition of self-delivery and outsourcing transportation costs, we develop a model to minimize the total cost of the logistics network by a jointly optimizing the distribution of facility locations and vehicle routing decision. The system includes fixed cost of self-vehicle and variable transportation costs, the fixed costs of distribution center construction, and the transportation costs of outsourcing. According to the characteristics of the problem, the hierarchical coding method is designed for genetic algorithm. Through the simulation example, the proposed strategy is compared with the traditional complete self-delivery and outsourcing operation mode. The results show that the proposed strategy could effectively reduce the additional cost of self-delivery and the construction cost of the distribution center, thus reducing the system cost. Our proposed is experimentally proved to reduce the system cost by 8.08% and 25.03% compared to the complete self-delivery and outsourcing operation mode, respectively. Finally, the impact of different outsourcing price on the systematic decisions is investigated by sensitivity analysis.

译

关键词

交通运输经济; 定位运输线路规划; 外包策略; 时间窗; 遗传算法

译

Keywords

transportation economy; location routing problem; outsourcing distribution; time window; genetic algorithm

译

目前国内外对于车辆路径问题研究较多，但对定位运输问题关注较少，定位运输线路安排问题是车辆路径问题的拓展。1959年Dantzig和Ramser^[

1]在针对运输问题的研究过程中，首次探讨了车辆路径问题。随后，众多学者从不同角度对该问题进行了深入的探讨。例如：Yu和Lin^{[参考文献 2

百度学术

2]} 构建了涉及外包配送的无车辆返回式定位运输模型，并运用了模拟退火算法开展研究；Marinakis^{[参考文献 3

百度学术

3]}提出了随机需求下的定位运输问题；Rui等^{[参考文献 4

百度学术

4]}设计了一种混合式的遗传算法对该问题进行拓展；Riquelme-Rodríguez等^{[参考文献 5

百度学术

5]}针对露天煤矿区的水库选址探讨了带库存约束的定位运输问题；Yakici^{[参考文献 6

百度学术

6]}将定位运输问题运用到无人机的飞行路径规划上；Moshref-Javadi等^{[参考文献 7

百度学术

7]}提出了以最小化等待时间为目标的定位运输问题，该模型能应用到灾后救援中；Schiffer与Walther等^{[参考文献 8

百度学术

8]}探讨了电动汽车商业化环境下带充电设施选址的定位运输问题；Guo和Zhang^{[参考文献 9

百度学术

9]}开展了关于车辆路径问题（VRP）和定位运输问题（LRP）的逆向物流（RL）的研究，并针对相应的模型和问题选取了人工蜂群算法进行研究，提出了一种领域贪婪调整的改进求解思路；Zhang等^{[参考文献 10

百度学术

10]}重点研究了车辆路径问题中的涉及饱和异构车队容量限制和二维负载约束条件的车辆路径规划，构建了2L-HFCVRP模型，以及相应的混合式求解算法；付旭辉等^{[参考文献 11

百度学术

11]}利用模式系数来改善遗传算法早熟现象；张潜等^{[参考文献 12-13

12-13]}利用遗传算法求解了定位运输模型；王正国等^{[参考文献 14

百度学术

14]}研究了在行车速度为时变的情况下的车辆路径问题；王绍仁和马祖军^{[参考文献 15

百度学术

15]}将定位运输问题应用在灾后应急响应中；王永等^{[参考文献 16

百度学术

16]}也针对地震后的定位运输问题进行了分析；王占中等^{[参考文献 17

百度学术

17]}等运用多层编码形式的遗传算法对危险品的指派调度进行了研究，染色体的编码设计中包含了两层的指派信息。李珍萍等^{[参考文献 18

百度学术

18]}结合成品油运输中出现的隔仓限制，卸载顺序限制等多重实际情况，开展了成品油二次运输的车辆路径问题研究，为石油公司解决实际问题提供了依据。然而，目前国内外有关定位运输问题的研究均采用全部车辆自营模式或全部外包的形式，尚未充分考虑实际运营中存在外包配送业务，以及外包配送对物流系统优化的影响。

译

相比现有的企业单一物流模式，通过自营与外包配送策略相结合的网络拓展模式，可以更容易地在较短时间内实现业务的网点覆盖，从而提高企业的市场占有率。鉴于此，本文提出联合外包策略的定位运输问题，通过将一部分配送任务外包给从事配送业务的企业增加货物运输的灵活型并降低系统成本，以期为物流系统整合设计提供参考。

译

1 联合外包策略的定位运输问题分析

对比于传统的定位运输线路规划网络，假设客户点（需求点）的需求既可以采用完全外包的方式由第三方企业来完成，也可以采用自送和外包联合的形式完成需求量供给，外包车辆可以从配送中心取货后送往各客户点，并且无需返回配送中心（如图1所示），即不存在回程车调度问题。联合外包运输的定位运输问题的目标是：确定使用的配送服务中心的数量和位置、自营车辆的配送路径，以及对应自送和外包配送的运输量，追求整个物流网络的总成本最小化。

译

图 1自送路径和外包路径的差别

Fig.1 The difference between self-delivery and outsourcing path

下载: 原图 | 高精图 | 低精图

对于该联合外包运输的定位运输问题的模型构建中，假设有 $R$ 处可能利用的服务中心的设施点，用 $G \{r | r = 1, \dots, R\}$ 来表示服务中心的集合；对于服务的客户点假设网络中有 $N$ 个，用 $H \{i | i = R + 1, \dots, R + N\}$ 来表示客户点或称为需求点的位置集合；用 $S \{G\} ⋃ \{H\}$ 来表示服务中心与客户点的位置集合；在该服务运输网络中假设有 $k$ 辆车，并用 $V \{v_{k} | k = 1, \dots, K\}$ 来表示运输工具能通过的路径或是道路。构建的模型中运用到的其它符号及其含义如下： $C_{i j}$ 表示从某一点i到另一点j的单位距离运输花费成本； $F_{r}$ 表示当在某一地点r处设立一个设施点所需要的建设成本； $q_{j}$ 表示某一需要服务的位置点所需自送运输的平均估计需求量； $Q_{k}$ 表示某一运输工具的容量； $d_{i j}$ 表示从位置点i到另外一个位置点j的运输行走距离； $X_{r j k}, X_{r m k}$ 表示某一个车辆k从设施点r朝目标服务点j、m出发完成服务，当车辆行驶时是1，没有车辆行驶则为0； $F$ 表示当运输由第三方物流公司负责，即采用外包策略时收取的每单位每公里货物的运输价格； $O_{i}$ 表示某一位置点i的货物需求量由外包运输完成的部分； $D_{i}$ 表示某一位置点i的全部货物需求量； $l_{n i}$ 表示某一位置点i距离某一个设施点n的距离； $y_{i}$ 表示规划处的运输路径上到达i点的次序； $C_{k}$ 表示使用第k辆车辆所对应的固定成本； $a_{i}$ 表示规定的开始服务需求点i的最早时间又称之为时间窗上限； $s_{i}$ 表示服务车辆到达需要服务的需求点i的时间； $b_{i}$ 表示规定的开始服务需求点i的最晚时间又称之为时间窗下限； $α_{i}$ 表示车辆提前到达需求点i进行等待的时间惩罚成本； $β_{i}$ 表示车辆到达需求点i迟到的时间惩罚成本； $t_{i j}$ 表示车辆从需求点i到达需求点j的走行时间； $f_{i}$ 表示车辆在i点进行服务的时间。

译

联合外包策略的定位运输问题数学模型中，包含三个决策变量 $X_{k}$ 、 $X_{i j k}$ 、 $Z_{r}$ ，其赋值情况如下：

译

$X_{k} = \{\begin{matrix} 当第 k 辆车辆被使用时, 取值为 1 \\ 否则, 0 \end{matrix}$

$X_{i j k} = \{\begin{matrix} 当 k 车从点 i 到达另一点 j 时, 取值为 1 \\ 否则, 0 \end{matrix}$

$Z_{r} = \{\begin{matrix} 当在某点 r 建设设施点时, 取值为 1 \\ 否则, 0 \end{matrix}$

对于本文构建的联合外包策略的定位运输线路规划问题模型，其物流网络的总成本主要包括自营车辆的固定成本和可变运输成本、配送服务中心建设的固定成本、外包配送的总成本、以及时间窗约束所带来的延误惩罚成本。因此，模型的目标函数表示如下：

译

$f (x) = m i n [\sum_{i \in S} \sum_{j \in S} \sum_{k \in V} C_{i j} X_{i j k} d_{i j} + \sum_{k \in V} C_{k} X_{\begin{matrix} k \end{matrix}}$

$+ \sum_{r \in G} F_{r} Z_{r} + \sum_{n \in G} \sum_{i \in H} F l_{n i} O_{i} + T_{i} (t_{i})]$

（1）

$T_{i} (t_{i}) = \sum_{i \in S} α_{i} m a x [(a_{i} - s_{i}), 0]$

$- \sum_{i \in S} β_{i} m a x [(s_{i} - b_{i}), 0]$

(2)

s.t.

译

$\sum_{i \in S} \sum_{k \in V} X_{i j k} \leq 1, \forall j \in H$

(3)

$\sum_{j \in S} \sum_{k \in V} X_{i j k} \leq 1, \forall i \in H$

(4)

$\sum_{i \in S} X_{i p k} - \sum_{j \in S} X_{p j k} = 0, \forall k \in V, p \in S$

(5)

$\sum_{r \in G} \sum_{j \in H} X_{r j k} \leq 1, \forall k \in V$

(6)

$\sum_{j \in S} \sum_{i \in H} q_{j} X_{i j k} \leq Q_{k}, \forall k \in V$

(7)

$q_{i} + O_{i} = D_{i}, \forall i \in H$

(8)

$\sum_{k \in k} X_{r m k} + Z_{r} + Z_{m} \leq 2, \forall m \in G, r \in G$

(9)

$M \cdot \sum_{j \in G} \sum_{k \in V} X_{i j k} \geq q_{i}, \forall i = R + 1, \dots, R + N$

(10)

$\sum_{k \in V} \sum_{j \in H} X_{r j k} - Z_{r} \geq 0, \forall r \in G$

(11)

$\sum_{j \in H} X_{r j k} - Z_{r} \leq 0, \forall k \in V, r \in G$

(12)

$y_{i} - y_{j} + (R + N) \cdot X_{i j k} \leq R + N - 1,$

(13)

$\forall R + 1 \leq i \neq j \leq R + N, k \in V$

$s_{i} + f_{i} + t_{i j} - M (1 - X_{i j k}) \leq s_{j},$

(14)

$\forall i, j \in S, k \in V$

$X_{i j k} = 0,1, \forall i, j \in S, k \in V$

(15)

$Z_{r} = 0,1, \forall r \in G$

(16)

$X_{k} = 0,1, \forall k \in V$

(17)

式（3）和（4）表示除了配送中心之外的所有客户点都只有一部车进出，即一个客户点只能由一部车来服务。考虑到某些客户点的配送将全部由外包服务完成，而出现这些需求点无自营车辆服务的情况，因而约束式的条件为小于等于1；式（5）表示驶入和驶出某客户点的车辆必须为同一辆，当这个点是配送中心时表示这部车从配送中心出发，服务完之后回到配送中心。当这个点是客户点时，表示进出这个需求点为同一辆车；式（6）表示某一辆车最多被一个仓库使用，只能从一个仓库驶出；式（7）表示一条线路上所有客户点自送的需求总量不能超过车辆的容量限制；式（8）表示每个客户点的需求量都应该被满足；式（9）表示任意两个仓库之间没有其他线路的连接方式；式（10）表示所有需要自送的客户点必须有车辆进行服务；式（11）和（12）表示每个运输工具只能从一个仓库出发有且只有一个起点；式（13）避免了子回路情况的出现；式（14）表示车辆的到达时间和与之对应时间窗的约束，保证车辆的到达时间加上服务时间以及两个客户点的行驶时间小于下一点的服务时间；式（15）、（16）以及（17）为0-1变量限制、非零变量限制及整数限制。

译

2 求解算法

对于这类NP难题的求解，遗传算法^[

4,11-13,17,20]、蚁群算法^{[参考文献 19

百度学术

19]}、人工蜂群算法^{[参考文献 9

百度学术

9]}等都在不同的应用场景中体现出了这类启发式算法的优越性。本文研究的模型中由于增加了配送中心选址和外包运输的路径决策，因而与传统的定位运输问题相比，该模型的算法复杂性将大大增加。本文利用改进的遗传算法进行求解，根据问题的特征，设计一种含运输量的多段编码遗传算法以映射配送中心选址，自送和外包运输车辆任务车辆路径决策。

译

2.1　染色体编码的设计

针对联合外包的定位运输问题，采用实数编码进行染色体的编写，当有N个需求点、以及最多 $K$ 辆货车时染色体分段编码设计如表1所示。

译

表 1 染色体编码设计

Table 1 Chromosome coding design

染色体编码分段	第一段	第二段	第三段	第四段
包含基因位数	N位	N位	N位	K位
分段染色体对应含义	使用车辆的编号	服务的顺序编号	需求点对应的自送量	设施点编号

下载: CSV

下载: 表格图片

该染色体的设计一共分为四段，一共有N+N+N+K个基因位。第一段的N个基因位用来表示每个客户点使用的车辆，每个客户点均有一个对应的基因位，这个基因位上数字表示相应的客户点使用的车辆编号。第二段的N个基因位表示对应的各客户点的服务顺序，通过对基因位上的自然数排序，得到对应客户点的服务顺序。第三段的基因位表示相应客户点的自送需求量。最后的第四段染色体，每个基因位上的数字表示对应车辆的出发和返回的设施点。

译

下面通过举例来说明该染色体的编码和解码方式，假设有一物流网络使用四辆车即K=4，有三个客户点即N=3，和两个设施点即R=2。某一染色体如图2所示：

译

图2 某一染色体构成范例

Fig. 2 Example of a chromosome composition

下载: 原图 | 高精图 | 低精图

利用表2～4对图1的染色体进行解码，首先根据给出的染色体找出每个基因位所代表的需求点的编号以及对应车辆的编号，随后对于染色体的第一段进行解码，可以得到对应车辆1、4所服务的需求点。随后利用染色体的第四段，根据车量的使用情况找出对应的车辆出发和终止的配送中心编号。利用第二段染色体，则可以得到对应的

译

表 2 该染色体基因位的代表含义

Table 2 Shows the meaning of the chromosome locus

基因值	第一段			第二段			第三段			第四段
基因值	1	1	4	2	1	3	10	20	10	1	1	1	2
基因位	1	2	3	4	5	6	7	8	9	10	11	12	13
对应代表	客1	客2	客3	客1	客2	客3	客1	客2	客3	车1	车2	车3	车4

下载: CSV

下载: 表格图片

表3 染色体的解码

Table 3 Chromosome decoding

车辆

配送的需求点

对应配送中心

最终解码

配送路径

合计

自送量

车1

1，2

配1

配1→2→1→配1

10+20=30

车4

配2

配2→3→配2

下载: CSV

下载: 表格图片

表4 该染色体对应自送与外包的情况

Table 4 The chromosome corresponds to the situation of self-delivery and outsourcing

运输量情况	需求点1	需求点2	需求点3
自送量	10	20	10
总需求量（已知）	20	20	20
外包量=总需求量-自送量	10	0	10

下载: CSV

下载: 表格图片

具体配送路径，第二段染色体提供了每个需求点的服务顺序，于是得出最终的自送的配送路径为配1→2→1→配1。最后利用染色体的第三段可以得到自送量和外包量。

译

2.2　对染色体约束条件的设计

通过对于染色体的编码设计完成对于车辆数量、服务次序、单独车辆服务对应需求点、自送量与外包量的和为总需求量等的约束限制，针对无法利用编码设计实现的限制，如对于车辆配送路径的最长限制和车辆的最高运输量的限制，通过设置惩罚函数的形式来实现。

译

2.3　计算每条染色体的适应度

适应值代表了对应染色体的存活概率的大小，本文可利用目标函数的值来表示对应染色体的适应值。适应函数的值充分考虑约束限制，利用惩罚函数来实现。如果某一种群中有n条染色体，则种群中的每条染色体的适应值用 $F_{i} (i \in n)$ 来表示。

译

2.4　遗传算子设计

2.4.1　染色体选择设计

染色的选择利用每条染色体对应的适应度采用轮盘赌选择方法进行选择，适应度越高的染色体被选中的概率越大。且将每一父代中的最优染色体加入子代中，进一步提高子代优良性。染色体被选中的概率为 $p_{i} = \frac{F_{i}}{\sum_{i = 1}^{n} F_{i}} (i \in n)$ ，此外产生的0至1随机数为 $r a n d_{i} (i \in n)$ 。如果 $p_{i} < r a n d_{i} (r a n d_{i} \in [0,1], i \in n)$ ，则第i条染色体被选中。

译

2.4.2　染色体交叉设计

利用双点交叉法来进行染色体的交叉，选取两条父代的染色体，在父代染色体上随机抽取两个基因位，随后将这两个基因位之间的染色体进行交叉互换。染色体交叉的概率需提前选定好。如果选出染色体的某一片段编码为C1（1 1 1 4），另一条的相应片段编码为C2（2 3 1 1），选出的两个基因位用下划线表示，交叉之后染色体编码为C1’（1 3 1 1），C2’（2 1 1 4）。

译

2.4.3　染色体变异设计

根据提前设置好的变异率，对于选出的染色体上两个抽取的基因位之间的变异段进行变异的操作，从而丰富染色体的多样性，避免求解的早熟和局部优化现象。上述例子中的C1（ 1 1 1 4 ）变异之后为C1”（ 1 4 3 2 ）。

译

3 算例分析

将某市某区的配送网络中各个成本的关系抽象为一个简单的联合外包配送网络，其中有14个等待服务的需求点，目前有4个可能新建的设施点（作为运载中心）。在满足每个需求点的需求量基础上，可以通过建设设施点进行自送，或者依靠外包策略进行外送。为了更好的刻画该运输网络中的内在关系并利于价格敏感性分析的开展，定义40 km为一个单位长度，即车辆行驶速度为1 单位长度/h。每部车辆的综合固定成本为10 元/天，自送的成本为1 元/40 km；由于该配送网络较小，每个点的距离比较近，外包运输服务提供商的外包成本价格为0.5 元/kg（非跨区小范围运输不考虑运输的距离，仅仅考虑运输量），自送车辆的最大运输距离为40 km，最大运输量为300 kg，一个设施点的建设成本以每日成本进行简单折算后为30 元。表5为14个待服务的需求点的相对位置坐标和需求量（kg），以及四个配送中心的相对位置坐标，该位置坐标已经过坐标换算，其中每1单位长度即为40 km，可利用欧式距离公式求得位置点之间的距离。表6表示每个待服务的需求点的时间窗限制和要求。

译

表 5 各个点的坐标和需求量

Table 5 Coordinates and demand for each point

编号	1	2	3	4	5	6
坐标	(18.7 15.29)	(12.21 14.5)	(20.07 10.14)	(19.39 13.37)	(25.27 14.24)	(22 10.04)
需求量	40	30	25	55	30	15
编号	7	8	9	10	11	12
坐标	(25.47 17.02)	(15.79 15.1)	(14.17 9.76)	(14.05 18.12)	(11.25 11.04)	(24 19.89)
需求量	40	25	30	20	25	35
编号	13	14	15配	16配	17配	18配
坐标	(19.41 18.13)	(22.11 12.51)	(17.53 17.38)	(16.6 12.38)	(23.52 13.45)	(16.47 8.45)
需求量	30	50	0	0	0	0

下载: CSV

下载: 表格图片

表 6 需求点的时间窗要求

Table 6 Time window requirements for demand points

编号	1	2	3	4	5	6	7
时间窗上限	8:00	5:00	4:06	1:30	6:00	6:30	13:54
时间窗下限	11:00	10:30	12:54	10:54	19:36	10:48	19:48
服务时间	0:12	0:48	0:24	0:06	0:42	0:18	0:12
编号	8	9	10	11	12	13	14
时间窗上限	10:06	15:30	2:30	10:12	13:00	2:18	15:12
时间窗下限	12:00	3:06	19:54	15:36	20:18	6:30	00:00
服务时间	0:12	0:18	0:18	0:06	0:30	0:30	0:36

下载: CSV

下载: 表格图片

设置染色体长度为50个基因位，初始基因种群为80个，进行500次迭代，多次求解得出最优的可行解。如图3所示为最优的可行解的自送车辆走行路径，表7为该可行解的自送与外包运输量以及车辆时刻表。

译

图 3 联合外包策略的定位运输网络图

Fig. 3 Transport network map about location routing problem based on outsourcing strategy

下载: 原图 | 高精图 | 低精图

表 7 该可行解的自送与外包运输量以及车辆时刻表

Table 7 The feasible solution of the self-delivery, outsourcing, and Vehicle timetable

编号	1	2	3	4	5	6	7
自送量	38	30	25	55	29	15	40
外包量	2	0	0	0	1	0	0
自送到达时刻	8:00	5:00	4:00	10:14	12:03	6:25	15:32
编号	8	9	10	11	12	13	14
自送量	24	30	20	0	35	0	48
外包量	1	0	0	25	0	30	2
自送到达时刻	13:38	16:41	9:51	-	18:58	-	20:40

下载: CSV

下载: 表格图片

该联合外包策略下的可行解对应自送车辆的运输路径为车辆1：18-3-6-5-7-12-18，车辆2：18-2-10-8-14-18，车辆3：18-1-4-9-18。该可行解使用的配送中心个数为1，对应配送中心为18；使用的车辆数为3；总的成本为168.67元（包括自送成本、外包成本、固定成本、时间惩罚成本等）。

译

其它10次求解的结果如表8所示。十次求解结果的最大值、最小值、均值、方差、以及均方差列入表9，根据计算结果可以看出该遗传算法的求解情况比较良好，多次求解结果的差距较小，均方差为5.6左右。

译

表8 遗传算法多次计算求解的情况

Table 8 Genetic algorithm to calculate the situation of multiple calculations

计算的次数	1	2	3	4	5	6	7	8	9	10
运输成本/元	179.17	188.77	181.44	184.11	168.67	177.74	181.48	185.97	184.46	184.67

下载: CSV

下载: 表格图片

表9 计算结果的数据分析

Table 9 Data analysis of the results

最大值	最小值	均值	方差	均方差
188.77	168.67	181.65	28.25	5.60

下载: CSV

下载: 表格图片

针对该运输网络，如果采用完全自送的方式，在其他的基础数据和时间窗限制不变的情况下，利用遗传算法进行求解。并将联合外包运输策略、全部自送和全部外包的配送总成本整理如下表10所示，通过对比可知在该案例中，联合外包运输的总成本相对最低，在该算例中联合外包运输策略较完全自送模式成本降低8.08%，较完全外包模式成本降低25.03%。这是因为：通过外包策略可以有效的减少时间窗的限制、车辆最高运输量的限制、运输距离限制所带来的惩罚成本、以及配送中心的建设成本，从而抵消了较高的外包价格所带来的额外运输成本。

译

表10 不同配送方式成本对比

Table 10 Comparison of cost of different distribution methods

配送方式	全部自送	全部外包	联合外包策略
配送总成本/元	183.5	225	168.67

下载: CSV

下载: 表格图片

最后，通过敏感性分析考察车辆的综合固定成本、自送的成本、设施点的建设成本以及外包成本的定价对模型系统性能的影响。在相应的成本和定价减少80%、60%、55%、50%、25%和增加25%、50%、100%、150%、200%时，计算自送、外包运输量以及成本的变化，如表11~14所示。

译

表 11 不同车辆固定成本下的计算结果

Table 11 Calculation results for different vehicle fixed costs

车辆固定成本变动率/%	-80	-60	-55	-50	-25	0	+25	+50	+100	+150	+200
总自送量	320	343	374	385	317	389	365	378	281	283	262
总外包量	130	107	76	65	133	61	85	72	169	167	188
运输价格/元	162.07	163.10	168.08	165.88	172.171	168.67	181.94	181.03	202.16	216.22	222.22

下载: CSV

下载: 表格图片

表 12 不同设施点建设成本下的计算结果

Table 12 Calculation results for different facility construction costs

设施点建设成本变动率/%	-80	-60	-55	-50	-25	0	+25	+50	+100	+150	+200
总自送量	329	299	346	265	287	389	296	401	398	309	431
总外包量	121	151	104	185	163	61	154	49	52	141	19
运输价格/元	154.27	159.03	161.42	167.72	166.71	168.67	185.28	188.90	204.98	237.23	242.02

下载: CSV

下载: 表格图片

表 13 不同车辆自送成本下的计算结果

Table 13 Calculation results for different self-vehicle transportation costs

车辆自送成本变动率/%	-80	-60	-55	-50	-25	0	+25	+50	+100	+150	+200
总自送量	436	380	414	396	371	389	275	254	234	120	120
总外包量	14	70	36	54	79	61	175	196	216	330	330
运输价格/元	106.49	124.63	127.36	142.77	170.01	168.67	187.95	204.03	220.50	233.24	238.89

下载: CSV

下载: 表格图片

表 14 不同外包运输价格下的计算结果

Table 14 Calculation results for different outsourcing transportation prices

外包价格变动率/%	-80	-60	-55	-50	-25	0	+25	+50	+100	+150	+200
总自送量	0	0	0	0	244	389	404	399	415	423	421
总外包量	450	450	450	450	206	61	46	51	35	27	29
运输价格/元	45	90	101.25	112.5	160.94	168.67	190.9	182.09	216.81	200	206.05

下载: CSV

下载: 表格图片

从表11~12可以看出，车辆固定成本、施点建设成本的变动对于外包的影响较小。根据表13可知，随着车辆自送成本的增高，因外包运输价格相对低廉，将运输量转移能保证总成本最低。且根据表14数据可得，随着外包运输价格的上升，对应的总的外包运输量下降并趋于稳定，总的自送量上升并趋于稳定。该情况与实际情况吻合，证明该模型的适应性、实用性良好。

译

4 结　论

考虑实际运营中存在的外包配送业务对定位运输的影响，设计了基于遗传算法的分段编码映射配送中心选址、以及自送和外包运输车辆路径联合决策求解方法。并通过算例验证了联合外包策略的模式相对于完全自送和完全外包模型具有一定的经济优势，能够减少整个运输网络的成本，并结合敏感性分析揭示了外包策略与定位运输之间的相互作用。后续可开展的研究包括：1）考虑配送中心库存对物流系统规划的影响，将问题拓展为库存定位运输问题；2）结合当前绿色新能源车辆的发展趋势，将问题拓展为电动车与柴油车混合模式下的定位运输问题。

译

参考文献

DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91. [百度学术]

YU V F, LIN S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computers & Operations Research, 2014, 62(2):184-196. [百度学术]

MARINAKIS Y. An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands[J]. Applied Soft Computing, 2015, 37(C):680-701. [百度学术]

RUI B L, FERREIRA C, SANTOS B S. A simple and effective evolutionary algorithm for the capacitated location–routing problem[J]. Computers & Operations Research, 2016, 70(C):155-162. [百度学术]

RIQUELME-RODRÍGUEZ J, GAMACHE M, LANGEVIN A. Location arc routing problem with inventory constraints[J]. Computers & Operations Research, 2016, 76:84-94. [百度学术]

YAKICI E. Solving location and routing problem for UAVs[J]. Computers & Industrial Engineering, 2016, 102:294-301. [百度学术]

MOSHREF-JAVADI M, LEE S. The latency location-routing problem[J]. European Journal of Operational Research, 2016, 255(2):604-619. [百度学术]

SCHIFFER M, WALTHER G. The electric location routing problem with time windows and partial recharging[J]. European Journal of Operational Research, 2017, 260(3):995-1013. [百度学术]

GUO K, ZHANG Q S. A discrete artificial bee colony algorithm for the reverse logistics location and routing problem[J]. International Journal of Information Technology & Decision Making, 2017, 16(2):1-19. [百度学术]

ZHANG D, DONG R, SI Y W, et al. A hybrid swarm algorithm based on ABC and AIS for 2L-HFCVRP[J]. Applied Soft Computing, 2018, 64:468-479. [百度学术]

付旭辉,康玲.遗传算法的早熟问题探究[J].华中科技大学学报(自然科学版),2003,7:53-54. [百度学术]

FU X H, KANG L. Study of the premature convergence of genetic algorithms[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition),2003,7:53-54. [百度学术]

张潜,高立群,胡祥培. 集成化物流中的定位运输路线安排问题(LRP)优化算法评述[J]. 东北大学学报,2003,1:31-34. [百度学术]

ZHANG Q, GAO L Q, HU X P. Review on optimal algorithms of location-routing problem (LRP) in integrated Logistics[J]. Journal of Northeastern University (natural science), 2003,1:31-34. [百度学术]

张潜,高立群,刘雪梅,等. 定位-运输路线安排问题的两阶段启发式算法[J]. 控制与决策,2004,7:773-777. [百度学术]

ZHANG Q, GAO L Q, LIU X M, et al. A two-phase heuristic approach to the location routing problem [J]. Control and Decision, 2004,7:773-777. [百度学术]

王正国,王红卫,刘会新.双目标时变速度车辆路径问题的模型及算法[J].华中科技大学学报(自然科学版),2005，34（12）:88-91. [百度学术]

WANG Z G, WANG H W, LIU H X. Mode for bi-objective time dependent vehicle routing problem and its algorithm[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition),2005，34（12）:88-91. [百度学术]

王绍仁,马祖军. 震害紧急响应阶段应急物流系统中的LRP[J]. 系统工程理论与实践,2011(8):1497-1507. [百度学术]

WANG S R, MA Z J. Location-routing problem in emergency logistics system for post-earthquake emergency relief response [J]. Systems Engineering-Theory & Practice, 2011(8):1497-1507. [百度学术]

王永,胥冬川,农兰晶.震后过渡阶段应急物流系统的定位-运输路线安排问题研究[J].计算机应用,2015,35(1):243-246. [百度学术]

WANG Y, XU D C, NONG L J. Research of location-routing problem in emergency logistics system for post-earthquake transitional stage[J]. Journal of Computer Applications,2015,35(1):243-246. [百度学术]

王占中,赵利英,曹宁博.基于多层编码遗传算法的危险品运输调度模型[J].吉林大学学报(工学版),2017,47(3):751-755. [百度学术]

WAND Z Z, ZHAO L Y, CAO N B. Hazardous material transportation scheduling model based on mutilayer coding genetic algorithm[J]. Journal of Jilin University (engineering and technology edition), 2017, 47(3):751-755. [百度学术]

李珍萍,周文峰,张煜炜,等.考虑卸载顺序约束的成品油二次配送车辆路径问题研究[J/OL].控制与决策，2019-05-08 [2019-07-07]. https://doi.org/ 10.13195/j.kzyjc.2 018 .1756. [百度学术]

LI Z P, ZHOU W F, ZHANG Y W, et al. Research on vehicle routing problem of refined oil secondary distribution considering unloading sequence constraints [J/OL]. Control and Decision，2019-05-08 [2019-07-07].https://doi.org/10.13195/j. kzyjc.2018.1756. [百度学术]

黄震,罗中良,黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报(自然科学版),2015,54(1):41-46. [百度学术]

HUANG Z, LUO Z L, HUANG S W. Application research of hybrid ant colony algorithm in vehicle routing problem with time windows [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015,54(1):41-46. [百度学术]

靳文舟,李鹏,巫威眺.基于多源公交数据和车时成本优化的公交运营时段划分方法[J].中国公路学报,2019,32(2):143-154. [百度学术]

JIN W Z, LI P,WU W T. Time-of-day interval partition method for bus schedule based on multi-source data and fleet-time cost optimization [J]. China Journal of Highway and Transport, 2019,32(2):143-154. [百度学术]

摘要

Abstract

with the objective to reduce the logistics system cost via partially outsourcing vehicle tasks. Considering the constraints in actual operation such as time windows

and the composition of self-delivery and outsourcing transportation costs

we develop a model to minimize the total cost of the logistics network by a jointly optimizing the distribution of facility locations and vehicle routing decision. The system includes fixed cost of self-vehicle and variable transportation costs

the fixed costs of distribution center construction

and the transportation costs of outsourcing. According to the characteristics of the problem

the hierarchical coding method is designed for genetic algorithm. Through the simulation example

the proposed strategy is compared with the traditional complete self-delivery and outsourcing operation mode. The results show that the proposed strategy could effectively reduce the additional cost of self-delivery and the construction cost of the distribution center

thus reducing the system cost. Our proposed is experimentally proved to reduce the system cost by 8.08% and 25.03% compared to the complete self-delivery and outsourcing operation mode

respectively. Finally

the impact of different outsourcing price on the systematic decisions is investigated by sensitivity analysis.

关键词

交通运输经济定位运输线路规划外包策略时间窗遗传算法

Keywords

transportation economylocation routing problemoutsourcing distributiontime windowgenetic algorithm

references

DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91.

YU V F, LIN S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computers & Operations Research, 2014, 62(2):184-196.

RUI B L, FERREIRA C, SANTOS B S. A simple and effective evolutionary algorithm for the capacitated location–routing problem[J]. Computers & Operations Research, 2016, 70(C):155-162.

RIQUELME-RODRÍGUEZ J, GAMACHE M, LANGEVIN A. Location arc routing problem with inventory constraints[J]. Computers & Operations Research, 2016, 76:84-94.

YAKICI E. Solving location and routing problem for UAVs[J]. Computers & Industrial Engineering, 2016, 102:294-301.

MOSHREF-JAVADI M, LEE S. The latency location-routing problem[J]. European Journal of Operational Research, 2016, 255(2):604-619.

SCHIFFER M, WALTHER G. The electric location routing problem with time windows and partial recharging[J]. European Journal of Operational Research, 2017, 260(3):995-1013.

ZHANG D, DONG R, SI Y W, et al. A hybrid swarm algorithm based on ABC and AIS for 2L-HFCVRP[J]. Applied Soft Computing, 2018, 64:468-479.

付旭辉,康玲.遗传算法的早熟问题探究[J].华中科技大学学报(自然科学版),2003,7:53-54.

FU X H, KANG L. Study of the premature convergence of genetic algorithms[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition),2003,7:53-54.

张潜,高立群,胡祥培. 集成化物流中的定位运输路线安排问题(LRP)优化算法评述[J]. 东北大学学报,2003,1:31-34.

ZHANG Q, GAO L Q, HU X P. Review on optimal algorithms of location-routing problem (LRP) in integrated Logistics[J]. Journal of Northeastern University (natural science), 2003,1:31-34.

张潜,高立群,刘雪梅,等. 定位-运输路线安排问题的两阶段启发式算法[J]. 控制与决策,2004,7:773-777.

ZHANG Q, GAO L Q, LIU X M, et al. A two-phase heuristic approach to the location routing problem [J]. Control and Decision, 2004,7:773-777.

王正国,王红卫,刘会新.双目标时变速度车辆路径问题的模型及算法[J].华中科技大学学报(自然科学版),2005，34（12）:88-91.

王绍仁,马祖军. 震害紧急响应阶段应急物流系统中的LRP[J]. 系统工程理论与实践,2011(8):1497-1507.

WANG S R, MA Z J. Location-routing problem in emergency logistics system for post-earthquake emergency relief response [J]. Systems Engineering-Theory & Practice, 2011(8):1497-1507.

王永,胥冬川,农兰晶.震后过渡阶段应急物流系统的定位-运输路线安排问题研究[J].计算机应用,2015,35(1):243-246.

WANG Y, XU D C, NONG L J. Research of location-routing problem in emergency logistics system for post-earthquake transitional stage[J]. Journal of Computer Applications,2015,35(1):243-246.

王占中,赵利英,曹宁博.基于多层编码遗传算法的危险品运输调度模型[J].吉林大学学报(工学版),2017,47(3):751-755.

李珍萍,周文峰,张煜炜,等.考虑卸载顺序约束的成品油二次配送车辆路径问题研究[J/OL].控制与决策，2019-05-08 [2019-07-07]. https://doi.org/ 10.13195/j.kzyjc.2 018 .1756https://doi.org/10.13195/j.kzyjc.2018.1756.

黄震,罗中良,黄时慰.一种带时间窗车辆路径问题的混合蚁群算法[J].中山大学学报(自然科学版),2015,54(1):41-46.

靳文舟,李鹏,巫威眺.基于多源公交数据和车时成本优化的公交运营时段划分方法[J].中国公路学报,2019,32(2):143-154.

浏览量

104

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种带时间窗车辆路径问题的混合蚁群算法

基于神经网络和遗传算法的桥梁参数优化方法与分析

基于改进遗传算法的非线性方程组求解

基于粒子群-投影寻踪和遗传-神经网络集成的预测模型

城市单路口交通信号两级模糊优化控制与仿真