王旭坪，张珺，易彩玉
关键词:
生产配送联合调度,在线订餐,多车多任务配送,三阶段启发式算法
摘要:
随着联通互联网的普及和生活节奏的推动，网上订餐因其独有的方便性和多样性，成为诸多下班族和中学生的新兴生活形式。截至2021年末，我国网上外卖用户规模达54416千人，环比下降29.92%。以“美团”为例，2021年餐饮外卖业务交易笔数144亿笔，环比下降41.6%，外卖市场潜力巨大。在实际运作中，线下酒楼对外卖订单的生产和配送环节常常分开调度，可使订单所需生产时间和配送时间最短。但是，外卖送达时间由开始生产时间、生产时长，开始配送时间和配送时长等诱因共同决定；同时，外卖订单信息提早未知、下单集中、配送地点分散等特性，致使外卖订单延误情况普遍。为此，有必要考虑外卖订单相关特点，研究外卖订单的生产和配送联合调度问题。
本文研究问题属于生产与配送联合调度（and，IPDS）的一类特殊问题。根据Chen[1]对IPDS通用表达式的定义，本文研究问题可叙述为。图1展示了外卖订单履行过程示意图：外卖订单实时下达；生产调度为多个面点师的并行机生产；配送汽车数和车容量有限，属于多车多任务汽车路径问题（Multi-Trips，MTVRP）；客户数有多个；目标函数为最小化所有订单的服务时间跨径之和。本文以所有订单的服务时间跨径之和为优化目标，建立并行机生产多车多任务配送联合优化物理模型。所需决策关键问题：（1）开始生产已下达的订单还是继续等待更多订单下达；（2）对已下达订单怎么委派给有限的面点师；（3）已完成的订单怎样生成配送批次及路径；（4）配送批次怎样分配给有限的汽车。
图1.外卖订单履行过程示意图
本文建立三阶段启发式在线调度算法对模型进行求解。总体设计思路：基于配送区域界定的混和时间窗分批策略对实时订单进行分批；同一批次内订单连续安排生产；将生产完批次委派配送汽车，并用遗传算法进行路径优化。采用数值实验将本文算法与传统生产配送在线调度算法进行对比剖析。研究表明：（1）当订单抵达率很小，饭店生产和配送能力充足时，可采用传统生产配送在线调度算法进行次序调度；当订单抵达率较大，饭店生产和配送能力受限制网上外卖订餐系统，适合采用三阶段启发式在线调度算法进行联合调度。（2）随着的减小，三阶段启发式在线调度算法对服务时间跨径之和的改进幅度越来越大。（3）三阶段启发式在线调度算法优势在于减短配送时间和配送等待时间网上外卖订餐系统，劣势在于引起了订单批次生成之前生产能力的空闲。（4）随着的减小，三阶段启发式在线调度算法的劣势渐渐减小，同时对于配送时间和配送等待时间的改进幅度也平缓减少。
本文构建模型及设计算法对网上订餐平台进行外卖订单调度具有较大应用价值，尤其适用于订单抵达率较高的外卖场景。生成的订单生产配送调度方案能帮助饭店优化生产配送资源，节省配送成本，提升配送效率。随着电子商务新业态的迅猛发展，网上商场、网购花束等新兴订单履行场景也符合生产配送在线联合调度问题的特点，本文构建的模型和算法同样适用于解决电商新业态中的订单履行问题。
基金捐助:
国家自然科学基金项目（，，，）
文章刊发:
《系统管理学报》2020,29(01):159-167.
作者介绍
免责声明：部分文章信息来源于网络以及网友投稿，本站只负责对文章进行整理、排版、编辑，出于传递更多信息之目的，并不意味着赞同其观点或证实其内容的真实性，如本站文章和转稿涉及版权等问题，请作者在及时联系本站，我们会尽快为您处理。
