[1]何梦军,吴怀岗,丁 翔.带时间窗的同城物流配送区域划分与路径优化[J].南京师范大学学报(工程技术版),2018,18(02):070.[doi:10.3969/j.issn.1672-1292.2018.02.010]
 He Mengjun,Wu Huaigang,Ding Xiang.City Logistics Distribution Region Division and PathOptimization with Time Windows[J].Journal of Nanjing Normal University(Engineering and Technology),2018,18(02):070.[doi:10.3969/j.issn.1672-1292.2018.02.010]
点击复制

带时间窗的同城物流配送区域划分与路径优化
分享到:

南京师范大学学报(工程技术版)[ISSN:1006-6977/CN:61-1281/TN]

卷:
18卷
期数:
2018年02期
页码:
070
栏目:
计算机与信息工程
出版日期:
2018-06-30

文章信息/Info

Title:
City Logistics Distribution Region Division and PathOptimization with Time Windows
文章编号:
1672-1292(2018)02-0070-07
作者:
何梦军1吴怀岗1丁 翔2
(1.南京师范大学计算机科学与技术学院,江苏 南京 210023)(2.南京大学政府管理学院,江苏 南京 210093)
Author(s):
He Mengjun1Wu Huaigang1Ding Xiang2
(1.School of Computer Science and Technology,Nanjing Normal University,Nanjing 210023,China)(2.School of Government,Nanjing University,Nanjing 210093,China)
关键词:
配送区域划分路径优化时间窗吸引子传播聚类法
Keywords:
distribution region divisionpath optimizationtime windowsaffinity propagation
分类号:
TP301.6; F252
DOI:
10.3969/j.issn.1672-1292.2018.02.010
文献标志码:
A
摘要:
同城物流的B2C和O2O包裹如何在短时间内以较少的资源配送到顾客手中,已成为物流管理中亟待解决的问题. 以最短配送时间为目标,构建带时间窗的“最后一公里”非线性数学规划模型(VRPTW),为求解此NP-hard问题,设计三阶段启发式算法,首先采用改进的吸引子传播聚类算法实现对配送区域的划分,充分考虑到配送点之间的关联因素; 再对同区域相似度较高的订单进行合并; 最后规划最短路径,从而建立完整的物流配送体系. 通过案例分析,验证了模型的有效性. 与传统的二阶段配送模型进行了对比,结果表明,三阶段算法能缩短订
Abstract:
How to send B2C and O2O packages to customers with short time and fewer resources in city logistics has become an urgent problem in logistics management. In this paper,we take the shortest delivery time as our goal,and build nonlinear mathematical programming model of the last mile with time windows. To solve this NP-hard problem,three-stage heuristic algorithm is designed. Firstly,an improved affinity propagation algorithm is used to realize the division of distribution,which fully takes the relationship between distribution points into consideration. Then,we merge orders with higher similarities in the same region. Finally, shortest paths are planned to establish a complete logistics distribution system. Through case analyses,the validity of the model is verified. The result shows that three-stage heuristic algorithm does better in reducing order completion time and waiting time,and in improving resource utilization than traditional two-stage delivery models.

参考文献/References:

[1] 郑棣. 电商物流“最后一公里”配送模式成本研究[J]. 物流科技,2015(9):139-141.
ZHENG D. The study of e-logistics last mile delivery optimal cost[J]. Logistics Sci-Tech,2015(9):139-141.(in Chinese)[2]崔珊珊,陈宏,俆加胜. 电商促销井喷需求下的应急商品配送研究[J]. 中国管理科学,2013(增刊1):141-147.
CUI S S,CHEN H,XU J S. The research on disruption commodity distribution based on explosive demand of e-commerce promotion[J]. Chinese journal of management science,2013(Suppl. 1):141-147.(in Chinese)
[3]TING C J,CHEN C H. Combination of multiple ant colony system and simulated annealing for the multidepot vehicle-routing problem with time windows[J]. Transportation research record journal of the transportation research board,2008(2089):85-92.
[4]ATHANASOPOULOS T,MINIS I. Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework[J]. Annals of operations research,2013,206(1):1-22.
[5]MATUSIAK M,KOSTER R D,KROON L,et al. A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse[J]. European journal of operational research,2014,236(3):968-977.
[6]葛显龙,许茂增,王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学,2013(1):125-133.
GE X L,XU M Z,WANG W X. Study on multi-types vehicle routing problem and its quantum genetic algorithm[J]. Chinese journal of management science,2013(1):125-133.(in Chinese)
[7]TA D,GENDREAU M,DELLAERT N,et al. Vehicle routing with soft time windows and stochastic travel times:a column generation and branch-and-price solution approach[J]. European journal of operational research,2014,236(3):789-799.
[8]于滨,靳鹏欢,杨忠振. 两阶段启发式算法求解带时间窗的多中心车辆路径问题[J]. 系统工程理论与实践,2012(8):1793-1800.
YU B,JIN P H,YANG Z Z. Two-stage heuristic algorithm for multi-depot vehicle routing problem with time windows[J]. Systems engineering-theory and practice,2012(8):1793-1800.(in Chinese)
[9]刘洪娟,甘明,姜玉宏,等. 基于遗传算法的配送中心选址及配送区域划分问题研究[J]. 物流技术,2010(8):43-46.
LIU H J,GAN M,JIANG Y H,et al. Research on distribution center allocation and distribution region division based on genetic algorithm[J]. Logistics technology,2010(8):43-46.(in Chinese)
[10]WANG Y,MA X,XU M,et al. Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm[J]. Expert systems with applications,2015,42(12):5019-5031.
[11]朱培芬,汉吉庆,杨华龙,等. 基于改进K-means算法的烟草配送区域划分[J]. 物流工程与管理,2009(6):84-85.
ZHU P F,HAN J Q,YANG H L,et al. Tobacco distribution area classification based on improved K-means algorithm[J]. Logistics engineering and management,2009(6):84-85.(in Chinese)
[12]李玉鹏,魏俊美,王召同,等. 冷链物流“最后一公里”快速配送方法研究[J]. 工业技术经济,2017(1):51-60.
LI Y P,WEI J M,WANG Z T,et al. Research on rapid delivery of "last mile" of cold-chain logistics[J]. Journal of industrial technological and economics,2017(1): 51-60.(in Chinese)
[13]王旭坪,张珺,马骏. 考虑完成期限的电子商务在线订单分批模型及算法[J]. 管理科学,2014(6):103-113.
WANG X P,ZHANG J,MA J. E-Commerce on-line order batching model and algorithm considering due time[J]. Journal of management science,2014(6):103-113.(in Chinese)
[14]BRUSCO M J,K(¨overO)HN H F. Comment on“clustering by passing messages between data points”[J]. Science,2008,319(5864):726.
[15]左静,帅斌,何凯妮,等. 基于改进熵权聚类SVD的铁路应急救援辅助决策方法[J]. 铁道学报,2017,39(8):18-26.
ZUO J,SHUAI B,HE K N,et al. Assistant decision-making method for railway emergency rescue based on modified entropy weight clustering SVD model[J]. Journal of the China railway society,2017,39(8):18-26.(in Chinese)
[16]RUAN J,WANG X,SHI Y. Developing fast predictors for large-scale time series using fuzzy granular support vector machines[J]. Applied soft computing,2013,13(9):3981-4000.

备注/Memo

备注/Memo:
收稿日期:2017-12-10.
基金项目:国家自然科学基金(71701090、71390521)、中国博士后基金(2017M621726)、江苏省社科基金(16JD009).
通讯联系人:吴怀岗,博士,副教授,研究方向:管理信息系统、物流与供应链. E-mail:05324@njnu.edu.cn
更新日期/Last Update: 2018-06-30