Abstract: The delays of online meal ordering delivery are currently serious. How to coordinate the production and distribution to minimize arrival time has become an urgent problem for online meal ordering during the peak period. Considering the fact that the order information are unknown in advance, a parallel machine production and multi-trip vehicle distribution joint optimization model was established to minimize the makespan of total orders. Besides, a three phase heuristic algorithm was proposed. Through a series of experiments where the orders were generated based on Poisson distribution (),the results were compared with those of the traditional algorithm. Several enlightening findings are discovered: when the order arrival rate, the makespan of total orders of the three phase heuristic algorithm is shorter. Meanwhile with the growth of order arrival rate, the improvement amplitude increases gradually. The model and algorithms proposed are conducive to generating efficiently production and distribution joint scheduling solution during the peak period.

Key words: integrated scheduling of production and delivery, online meal ordering, multi-trip vehicle routing and scheduling, three phase heuristic algorithm

摘要： 当前在线订餐配送延迟严重，如何协调生产和配送环节使快餐最快送达，已成为在线订餐亟待解决的问题。针对订单信息提前未知、厨师及配送车辆有限等特点，构建并行机生产多车多任务配送联合优化模型，以最小化所有订单的总服务时间跨度之和，并设计三阶段启发式在线调度算法进行求解。以某在线餐厅高峰期到达率服从泊松分布（）的订单进行数值实验，将三阶段启发式算法与传统算法实验结果进行比较。研究表明，当时，三阶段启发式算法的总服务时间跨度之和较短且对总服务时间跨度之和的优化幅度随值的增大而提高。构建的模型及算法有利于高峰期餐厅生成生产配送联合调度方案，优化生产配送资源。

关键词: 生产配送联合调度, 在线订餐, 多车多任务配送, 三阶段启发式算法