两个轴辐式网络协同建设的多层编码遗传算法

胡晶晶; 黄有方

doi:10.3969/j.issn.0258-2724.20190893

两个轴辐式网络协同建设的多层编码遗传算法

doi: 10.3969/j.issn.0258-2724.20190893

胡晶晶,
黄有方^,

基金项目: 上海市科学技术委员会科技基金（15dz1100900）；上海市科研计划专项（17DZ2280200）

详细信息

作者简介:
胡晶晶（1989—），女，博士研究生，研究方向为供应链智能分析，E-mail：jingjingnankai@sina.com

通讯作者:
黄有方（1959—），男，教授，博士生导师，博士，研究方向为物流信息系统、供应链智能分析与实现，E-mail：yhuang@shmtu.edu.cn

中图分类号: U492.3；TP183
计量
- 文章访问数: 637
- HTML全文浏览量: 401
- PDF下载量: 13
- 被引次数: 0
出版历程
- 收稿日期: 2019-09-19
- 修回日期: 2019-12-11
- 网络出版日期: 2019-12-15
- 刊出日期: 2020-10-01

Multi-layer Coded Genetic Algorithm with Collaborative Construction of Two Hub-and-Spoke Networks

HU Jingjing,
HUANG Youfang^,

摘要

摘要: 为了降低物流网络的建设成本投入，充分利用物流资源，提出轴辐式网络间的协同建设. 同时建设两个轴辐式物流网络，一个轴辐式网络为自己网络中的每一个枢纽从另一个轴辐式网络中选择一组协作枢纽，两个网络可以共同使用协作枢纽. 目标是使两个轴辐式网络的建设成本和它们之间的协作成本总和最小. 首先，运用混合整数规划模型描述所研究的问题；其次，根据问题的复杂度，设计了多层编码的遗传算法来解决问题，一条染色体分别表示了两个轴辐式网络；最后，在算例中进行了参数敏感性分析，分析参数对各部分成本和物流网络结构及协作枢纽的影响. 分析结果表明：在两个网络的协同建设中，一个网络中转移到另一个网络的流量大小对两个网络各自的网络结构和构建成本具有显著的影响；协同建设能够同时系统化地优化两个轴辐式网络，降低成本，整合物流资源.
- 协同建设 /
- 协作 /
- 多层编码遗传算法 /
- 轴辐式网络
Abstract: In order to reduce the construction cost of logistics network and make full use of logistics resources, the collaborative construction for hub-and-spoke networks is proposed. We designed the simultaneous construction of two hub-and-spoke logistics networks, in which one hub-and-spoke network selects a group of collaboration hubs from another hub-and-spoke network for each hub, and both networks can use collaboration hubs. The goal is to minimize the sum of the construction costs and collaboration costs of the two hub-and-spoke networks. First, the mixed integer programming model is used to describe the problem. Then, according to the complexity of the problem, a multi-layer coded genetic algorithm is designed to solve the problem. Finally, the parameter sensitivity analysis is carried out with a case to analyze the influences of the parameters on costs, logistics network structure and cooperation hub, in which one chromosome represents two hub-and-spoke networks. The analysis results show that in the collaborative construction of two networks, the amount of traffic transferred from one network to another has a significant impact on the network structure and construction cost of the two networks. Collaborative construction can systematically optimize two hub-and-spoke networks, reduces costs and effectively integrate logistics resources.
- collaborative construction /
- collaboration /
- multi-layer coded genetic algorithm /
- hub-and-spoke network

HTML全文

图 1 遗传算法设计框架

Figure 1. Genetic algorithm design framework

下载: 全尺寸图片幻灯片

图 2 编码和交叉方式

Figure 2. Genetic coding and crossover mode

下载: 全尺寸图片幻灯片

图 3 CN和TN的轴辐式网络结构（$\alpha = 2.5{\text{%}} ,\;\beta = 2.5$）

Figure 3. Hub-and-spoke network structure of CN and TN ($\alpha = 2.5{\text{%}} ,\;\beta = 2.5$)

下载: 全尺寸图片幻灯片

图 4 CN和TN的轴辐式网络结构（$\alpha \!=\!15.0{\text{%}} ,\;\beta = 2.5$）

Figure 4. Hub-and-spoke network structure of CN and TN ($\alpha = 15.0{\text{%}} ,\;\beta = 2.5$)

下载: 全尺寸图片幻灯片

图 5 CN和TN的网络节点重叠情况（$\alpha = 2.5{\text{%}} ,\;\beta = 2.5$）

Figure 5. Network nodes overlap of CN and TN ($\alpha = 2.5{\text{%}} ,\;\beta = 2.5$)

下载: 全尺寸图片幻灯片

图 6 CN和TN的网络节点重叠情况（$\alpha = 15.0{\text{%}} ,\;\beta = 2.5$）

Figure 6. Network nodes overlap of CN and TN ($\alpha = 15.0{\text{%}} ,\;\beta = 2.5$)

下载: 全尺寸图片幻灯片

图 7 遗传算法的收敛情况（$\alpha = 15.0{\text{%}} ,\;\beta = 2.5$）

Figure 7. Convergence of genetic algorithm ($\alpha = 15.0{\text{%}} ,\;\beta = 2.5$)

下载: 全尺寸图片幻灯片

图 8 CN成本随着参数 $\alpha $ 的变化趋势

Figure 8. Cost variation of CN with $\alpha $

下载: 全尺寸图片幻灯片

图 9 TN随着参数 $\alpha $ 的变化趋势

Figure 9. Cost variation of TN with $\alpha $

下载: 全尺寸图片幻灯片

图 10 CN和TN的协作成本随参数 $\alpha $ 的变化趋势

Figure 10. Cost variation of TN and CN with $\alpha $

下载: 全尺寸图片幻灯片

图 11 CN和TN的协作成本随参数 $\beta $ 的变化趋势

Figure 11. Collaboration cost variation of CN and TN with $\beta $

下载: 全尺寸图片幻灯片

表 1 参数 $\alpha $ 取值变化时CN和TN的枢纽选址和协作枢纽的计算结果

Table 1. Calculation results of hub location and collaboration hub of CN and TN with different values of $\alpha $

$\alpha $/%	CN的枢纽	TN的枢纽	协作枢纽
2.5	10，26，46，49，77，80，104，115，119，129，141，171，183，206，211，219，223，249，251，253，299，301，304，313，318，322，330，349，372，388，396，404，405，426，440，450，468，473，491，494	12，38，59，67，75，87，95，124，131，141	{26，46，49}，{119，141，171}，{206，223，249}，{119，171，183}，{141，171，219}，{223，249，253}，{223，249，253}，{372，396，404}，{349，372，405}，{396，404，405}
5.0	1，21，37，52，56，61，100，101，118，124，131，154，168，181，195，209，214，228，232，242，255，258，276，285，294，318，330，347，348，358，374，387，404，410，433，454，458，459，479，498	31，36，46，57，67，86，94，121，135，139	{118，131，168}，{100，101，195}，{118，154，168}，{131，168，181}，{168，181，228}，{232，255，258}，{232，255，258}，{348，374，387}，{358，374，410}，{374，387，404}
10.0	9，30，33，52，79，87，102，127，133，144，152，180，186，191，202，205，213，230，255，262，266，287，293，296，326，329，337，350，355，359，372，386，397，417，440，441，443，461，476，499	19，29，54，57，79，94，96，130，135，139	{52，87，127}，{79，102，152}，{180，186，202}，{180，186，202}，{205，230，255}，{230，255，262}，{262，266，337}，{372，386，397}，{350，372，417}，{372，386，397}
15.0	6，20，47，50，66，80，89，104，113，127，155，156，167，171，185，220，221，229，235，253，275，282，298，299，306，325，341，342，357，373，384，394，398，411，426，434，437，452，468，492	12，29，48，53，84，102，103，113，128，132	{20，47，50}，{80，104，156}，{155，171，185}，{167，171，185}，{221，253，275}，{253，275，325}，{275，325，373}，{342，357，398}，{394，398，411}，{384，394，411}
20.0	9，24，40，55，77，80，82，102，114，128，145，151，165，182，193，204，210，211，225，240，241，258，266，284，286，304，311，320，357，363，369，379，389，403，406，418，448，471，474，493	5，7，11，13，14，19，23，28，32 49	{9，24，77}，{9，77，82}，{24，40，55}，{24，40，55}，{77，82，151}，{40，77，82}，{77，82，151}，{145，151，204}，{55，114，128}，{145，151，204}

下载: 导出CSV

表 2 参数$\beta $ 取值变化时CN和TN的枢纽选址和协作枢纽的计算结果

Table 2. Calculation results of hub location and collaboration hub of CN and TN with different values of $\beta $

$\beta $	CN的枢纽	TN的枢纽	协作枢纽
0.5	14，16，31，53，63，86，102，109，127，151，156，165，191，194，205，217，224，233，239，243，273，282，290，321，324，333，335，337，351，352，354，364，396，401，404，434，446，471，490，498	15，32，42，54，65，82，91，116，132，141	{16，31，53}，{53，127，156}，{127，151，191}，{127，165，194}，{165，194，224}，{233，243，290}，{233，243，290}，{335，352，396}，{354，401，404}，{396，401，404}
2.5	9，16，32，50，62，63，77，107，115，130，135，154，174，183，189，209，214，232，244，251，258，276，279，288，303，321，342，349，351，357，369，389，390，401，408，432，461，482，483，488	11，34，36，52，67，91，94，121，130，131	{16，32，50}，{77，130，154}，{107，115，174}，{130，183，189}，{130，183，189}，{232，244，258}，{232，244，258}，{342，389，390}，{389，390，408}，{349，389，401}
4.5	9，30，47，55，73，87，93，131，133，143，157，167，186，194，206，213，219，221，247，251，258，263，297，300，308，320，321，340，364，366，368，374，391，413，435，444，473，474，483，489	19，32，48，66，71，95，106，126，134，136	{47，87，131}，{131，157，167}，{143，186，194}，{167，186，194}，{221，247，258}，{221，247，258}，{247，263，368}，{340，366，374}，{366，374，413}，{340，374，391}
6.5	7，16，41，52，58，94，97，114，130，135，149，164，170，196，209，220，227，236，238，239，255，259，305，307，326，328，336，340，344，369，375，381，405，409，428，432，448，457，470，486	9，36，37，69，70，75，94，123，135，143	{16，41，52}，{97，114，209}，{130，149，170}，{227，238，255}，{164，170，196}，{149，220，239}，{227，238，255}，{344，381，405}，{340，405，409}，{381，405，409}
8.5	9，24，41，46，63，82，94，107，125，133，147，149，171，196，214，217，221，235，247，261，267，276，281，282，294，298，312，328，354，363，383，387，400，416，433，443，459，460，478，493	13，29，51，60，64，86，98，121，137，147	{41，46，63}，{63，107，147}，{149，214，235}，{149，171，196}，{125，171，196}，{247，261，267}，{247，261，267}，{363，383，387}，{363，383，387}，{363，400，416}

下载: 导出CSV

表 3 参数$\alpha $和$\beta $取值变化时各个成本的计算结果

Table 3. Calculation results of each cost with different values of $\alpha $ and $\beta $

参数		costCN/ × 10¹²	costTN/ × 10¹¹	costCol/ × 10⁹	costTotal/ × 10¹²
α	2.5%	5.40	5.01	2.26	5.900
	5.0%	5.72	4.80	4.46	6.210
	10.0%	5.52	4.88	8.93	0.009
	15.0%	5.86	4.75	13.40	6.340
	20.0%	6.00	−14.00	19.20	4.620
β	0.5	5.66	5.00	4.39	6.160
	2.5	5.50	4.74	4.46	5.980
	4.5	5.50	4.92	4.65	6.000
	6.5	5.59	5.46	4.67	6.140
	8.5	5.44	5.06	4.85	5.950

下载: 导出CSV

参考文献(11)

MARTINS DE SÁ E, CONTRERAS I, CORDEAU J F. Exact and heuristic algorithms for the design of hub networks with multiple lines[J]. European Journal of Operational Research, 2015, 246(1): 186-198. doi: 10.1016/j.ejor.2015.04.017

李靖,张永安. 基于ISM 的物流网络协同效应影响因素分析−以苏宁电器为核心的物流网络为例[J]. 北京交通大学学报(社会科学版),2011,10(4): 45-52. doi: 10.3969/j.issn.1672-8106.2011.04.009

LI Jing, ZHANG Yong'an. An analysis of the affecting factors of collaborative effectof the logistics networks:a case study of Suning's core logistics networks[J]. Journal of Beijing Jiaotong University (Social Sciences Edition), 2011, 10(4): 45-52. doi: 10.3969/j.issn.1672-8106.2011.04.009

陈誉文. 协同物流网络资源需求与配送中心运输调度的建模优化[D]. 上海: 上海交通大学, 2009.

单丽辉,张仲义,王喜富,等. 基于系统理论的物流网络分析与资源整合[J]. 北京交通大学学报(社会科学版),2011,10(2): 47-53. doi: 10.3969/j.issn.1672-8106.2011.02.008

SHAN Lihui, ZHAN Zhongyi, WANG Xifu, et al. Analysis of logistics network and resources integration based on system theory[J]. Journal of Beijing Jiaotong University (Social Sciences Edition), 2011, 10(2): 47-53. doi: 10.3969/j.issn.1672-8106.2011.02.008

HAFEZALKOTOB A. Competition,cooperation,and coopetition of green supply chains under regulations on energy saving levels[J]. Transportation Research Part E: Logstics and Transformatim Review, 2017, 97: 228-250. doi: 10.1016/j.tre.2016.11.004

CUI L, HERTZ S. Networks and capabilities as characteristics of logistics firms[J]. Industrial Marketing Management, 2011, 40(6): 1004-1011. doi: 10.1016/j.indmarman.2011.06.039

DEFRYN C, SÖRENSEN K. Multi-objective optimisation models for the travelling salesman problem with horizontal cooperation[J]. European Journal of Operational Research, 2018, 267(3): 891-903. doi: 10.1016/j.ejor.2017.12.028

WANG Y, PENG S, XU C, et al. Two-echelon logistics delivery and pickup network optimization based on integrated cooperation and transportation fleet sharing[J]. Expert Systems with Applications, 2018, 113: 44-65. doi: 10.1016/j.eswa.2018.06.037

SHEKHTMAN L M, DANZIGER M M, VAKNIN D. Robustness of spatial networks and networks of networks[J]. Comptes Rendus Physique, 2018, 19(4): 233-243. doi: 10.1016/j.crhy.2018.09.005

DAMGACIOGLU H, DINLER D, EVIN N, et al. A genetic algorithm for the uncapacitated single allocation planar hub location problem[J]. Computers & Operations Research, 2015, 62: 224-236.

史峰, 王辉, 郁磊, 等. MATLAB智能算法30个案例分析[M]. 北京: 北京航空航天大学出版社, 2011: 108-109.

施引文献

附加材料(0)

访问统计