货运O2O平台有时间窗同城零担集货匹配优化决策

李建斌, 周泰, 徐礼平, 戴宾

系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (4) : 978-988.

PDF(1354 KB)
中国科学院数学与系统科学研究院期刊网
PDF(1354 KB)
系统工程理论与实践 ›› 2020, Vol. 40 ›› Issue (4) : 978-988. DOI: 10.12011/1000-6788-2018-2300-11
论文

货运O2O平台有时间窗同城零担集货匹配优化决策

    李建斌1, 周泰1, 徐礼平1, 戴宾2
作者信息 +

Matching optimization decision of city LTL carpool based on time windows on the freight O2O platform

    LI Jianbin1, ZHOU Tai1, XU Liping1, DAI Bin2
Author information +
文章历史 +

摘要

零担集货业务的供需匹配和路线规划问题是同城货运O2O平台面临的发展难点.本文站在平台的角度，同时考虑司机和客户的实际需求，引入单位订单处理时间窗的概念，提出操作性较强的零担集货预匹配优化策略，突破传统"逐级推送模式"的思维局限，充分考虑需求和运力的属性-时间-空间分布；其次综合考虑客户OD点对、订单时间窗、以及司机工作时间窗、起终点、车辆容量限制等因素，在不考虑拒绝订单的条件下，以最小化服务总成本为优化目标，构建单位订单处理时间窗内某区域的半开放式多车场的带取送货和时间窗的车辆路径优化模型.最后针对模型特性采用改进的遗传算法进行求解，并选取卓集送公司某市某区某单位订单处理时间段（高峰期）连续60天的实例数据进行实证分析.研究结果表明，改进遗传算法的求解质量明显高于就近匹配贪婪算法，优化比例平均值为30%，最高达到53%，从而实现司机和客户双方的利益最大化.

Abstract

The majority of the freight O2O platforms are faced with the difficulties that matching supply and demand and planning routes in the development of LTL (less-than-truckload, LTL) carpool system. This paper simultaneously considers the demand of drivers and clients on platform's side to propose the optimized pre-matching policy which introduces the unit order-processing time window, breaking through the limitation of traditional "step by step pushing mode" and comprehensively considering the attribute-time-space distribution of demand and capacity. Then under the premise of considering the factors of clients' OD points, time windows and drivers' working time windows, start-end terminals and vehicle capacity, we construct the mathematical model which called the half-open multi-depot vehicle routing problem with pick-up and delivery and time windows, aiming at minimizing the total cost and without rejecting orders. Finally, we use the improved genetic algorithm to solve it based on its features, selecting the practical data of Zallsoon during the peak period (for 60 days) in a certain distinct to confirm the superiority and feasibility. The obtained results illustrate that improved genetic algorithm (comparing with "closely-matching greedy algorithm") can significantly reduce the total service cost by an average of 30% (up to 53%) and realize the maximization of interests of drivers and clients.

关键词

零担集货 / 供需匹配 / 路径优化 / 取送货 / 时间窗 / 改进遗传算法

Key words

LTL carpool / supply-demand matching / route optimization / pick-up and delivery / time windows / improved genetic algorithm

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
李建斌 , 周泰 , 徐礼平 , 戴宾. 货运O2O平台有时间窗同城零担集货匹配优化决策. 系统工程理论与实践, 2020, 40(4): 978-988 https://doi.org/10.12011/1000-6788-2018-2300-11
LI Jianbin , ZHOU Tai , XU Liping , DAI Bin. Matching optimization decision of city LTL carpool based on time windows on the freight O2O platform. Systems Engineering - Theory & Practice, 2020, 40(4): 978-988 https://doi.org/10.12011/1000-6788-2018-2300-11
中图分类号： U116.2   

参考文献

[1] 熊燕舞, 祁娟. 速派得:"拼货+整车"模式破局同城货运难题——速派得CEO江镇专访[J]. 运输经理世界, 2015(19):22-25.Xiong Y W, Qi J. "Package + vehicle" mode breaks the same city freight problem-Interview with CEO Jiang Zhen[J]. Transportation Manager World, 2015(19):22-25.
[2] 胡大伟, 陈诚, 郭晓汾. 带集货和配送的多站点VRP优化算法研究[J]. 数学的实践与认识, 2007, 37(2):98-104.Hu D W, Chen C, Guo X F. Research on optimal algorithm for multi-depot vehicle routing problem with pickups and deliveries[J]. Mathematics in Practice and Theory, 2007, 37(2):98-104.
[3] 余明珠, 李建斌, 雷东. 装卸一体化的车辆路径问题及基于插入法的新禁忌算法[J]. 中国管理科学, 2010, 18(2):89-95.Yu M Z, Li J B, Lei D. The research of VRP with pick-up and delivery and a new tabu search based on insertion method[J]. Chinese Journal of Management Science, 2010, 18(2):89-95.
[4] 杨鹏, 邹浩, 徐贤浩. 带时间窗集送货需求可分车辆路径问题的改进蚁群算法[J]. 系统工程, 2015, 33(9):58-62.Yang P, Zou H, Xun X H. Improved ant colony algorithm for vehicle routing problem with time windows and split pickups and deliveries[J]. Systems Engineering, 2015, 33(9):58-62.
[5] Allahyari S, Salari M, Vigo D. A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem[J]. European Journal of Operational Research, 2015, 242(3):756-768.
[6] Nagy G, Wassan N A, Speranza M G, et al. The vehicle routing problem with divisible deliveries and pickups[J]. Transportation Science, 2015, 49(2):271-294.
[7] Bartolini E, Bodin L, Mingozzi A. The traveling salesman problem with pickup, delivery, and ride-time constraints[J]. Networks, 2016, 67(2):95-110.
[8] 潘雯雯, 郭海湘, 周光勇, 等. 基于两阶段算法的需求可拆分多车型车辆路径问题[J]. 中国管理科学, 2016, 24(S1):55-61.Pan W W, Guo H X, Zhou G Y, et al. Research on split delivery and heterogeneous fleet vehicle routing problem based on two phase algorithm[J]. Chinese Journal of Management Science, 2016, 24(S1):55-61.
[9] 何小锋, 马良. 带时间窗车辆路径问题的量子蚁群算法[J]. 系统工程理论与实践, 2013, 33(5):1255-1261.He X F, Ma L. Quantum-inspired ant colony algorithm for vehicle routing problem with time windows[J]. Systems Engineering-Theory & Practice, 2013, 33(5):1255-1261.
[10] 朱玲玲, 程学云, 魏晓宁, 等. 基于Sweep和主动禁忌的多时窗VRPPD设计[J]. 计算机工程与设计, 2013, 34(9):3279-3283.Zhu L L, Cheng X Y, Wei X N, et al. Design for VRPPD with multi-time window based on sweep and reactive tabu[J]. Computer Engineering and Design, 2013, 34(9):3279-3283.
[11] 揭婉晨, 杨珺, 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践, 2016, 36(7):1795-1805.Jie W C, Yang J, Yang C. Branch-and-price algorithm for heterogeneous electric vehicle routing problem[J]. Systems Engineering-Theory & Practice, 2016, 36(7):1795-1805.
[12] 李阳, 范厚明, 张晓楠, 等. 求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法[J]. 系统工程理论与实践, 2018, 38(2):522-531. Li Y, Fan H M, Zhang X N, et al. Two-phase variable neighborhood tabu search for the capacitated vehicle routing problem with fuzzy demand[J]. Systems Engineering-Theory & Practice, 2018, 38(2):522-531.
[13] Qi M, Lin W H, Li N, et al. A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows[J]. Transportation Research Part E, 2014, 48(1):248-257.
[14] Rybickova A, Brodsky J, Karaskova A, et al. A genetic algorithm for the multi-depot vehicle routing problem[J]. Applied Mechanics & Materials, 2015, 803(3):69-75.
[15] 牟向伟, 陈燕, 高书娟, 等. 基于改进量子进化算法的车货供需匹配方法研究[J]. 中国管理科学, 2016, 24(12):166-176.Mu X W, Chen Y, Gao S J, et al. Vehicle and cargo matching method based on improved quantum evolutionary algorithm[J]. Chinese Journal of Management Science, 2016, 24(12):166-176.
[16] Afifi S, Dang D C, Moukrim A. Heuristic solutions for the vehicle routing problem with time windows and synchronized visits[J]. Optimization Letters, 2016, 10(3):511-525.
[17] Mancini S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet:Formulation and adaptive large neighborhood search based matheuristic[J]. Transportation Research Part C:Emerging Technologies, 2016, 70(9):100-112.
[18] Mahmoudi M, Zhou X. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows:A dynamic programming approach based on state-space-time network representations[J]. Transportation Research Part B, 2016, 89(7):19-42.
[19] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4):455-472.
[20] Baldacci R, Bartolini E, Mingozzi A. An exact algorithm for the pickup and delivery problem with time windows[J]. Operations Research, 2011, 59(2):414-426.
[21] 刘冉, 江志斌, 耿娜, 等. 半开放式多车场车辆路径问题[J]. 上海交通大学学报, 2010, 44(11):1539-1545.Liu R, Jiang Z B, Geng N, et al. The half open multi-depot vehicle routing problem[J]. Journal of Shanghai Jiao Tong University, 2010, 44(11):1539-1545.

基金

国家自然科学基金重点项目（71831007）；国家自然科学基金面上项目（71571079，71671133）
PDF(1354 KB)

771

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉