同城即时配送问题基于多预测场景的在线调度

同城即时配送是随现代电子商务而产生的新问题,该问题呈现出极强的动态性与求解时间的紧迫性,并具有商户与顾客一对多的关系、车辆需要多次往返商户取货、货物取送有时效要求等诸多新特征,无法依赖现有研究而求解.针对这一问题,建立了基于多预测场景的在线优化调度方法,将带有预测订单的多个场景整合到路线规划过程,通过每个场景的方案计算,以及多场景方案的整合,得到了车辆赖以运行的集成方案,提高了调度方案面对未来不确定需求的适应性;所建立的调度系统在新订单进入时立即响应,在系统闲置时则采用大邻域搜索技术不断优化未完成的任务方案.最后,在具有200～300个日订单的大连市某同城即时配送公司的真实数据上,验证了在线调度方法的有效性和可行性.

Online scheduling for the instant delivery problem in a city based on multiple prediction scenarios

The instant delivery problem in a city area is a new problem arising from the modern electronic commerce. This problem has many new features, e.g. strong dynamics, the urgency in solution time, the one-to-many relationship between retailers and customers, multiple returns of vehicles to retailers for pickups, and the timeliness requirements for pickups and deliveries. The problem cannot be solved by any existing methods. To solve the problem, an online scheduling method based on multiple prediction scenarios is presented. The method brings multiple scenarios, each of which has predicted orders, into the routing and scheduling procedure, and obtains an integrated solution by calculating the scheme of every scenario and integrating the schemes of all scenarios. Such a solution idea improves the elasticity of the scheduling solution to uncertain demands in the future. The proposed scheduling system can make a response immediately when any new order is placed, and optimize the sequence of uncompleted deliveries iteratively by using the large-scale neighborhood search when the system is idle. Finally, the validity and feasibility of the presented method are tested on the real data, which has about 200~300 orders per day and is obtained from an instant delivery company in Dalian City.