考虑真实场景动态事件的动态取送货问题

实时城市配送决策高度依赖于环境的变化，须及时处理配送系统中由各种动态事件带来的需求和环境变化. 综合考虑新请求逐渐出现、旧请求修改或取消、交通拥堵状况和车辆抛锚4种动态事件对车辆路径规划和配送服务的影响，重新建立考虑实时场景多项动态事件的取送货（DPDP-MDE）动态车辆路径规划模型. 设计动态算法框架求解该模型，给出调度时域内静态子问题执行规则和计算规则；针对具体静态子问题，采用构造型启发式算法生成初始可行解，分别采用禁忌搜索算法和自适应大规模邻域搜索算法2种智能优化算法，改善初始可行解质量；在更新路径规划方案时，运用未固定动态插入法，解决处于规划中的未固定请求和新请求同步处理问题. 数值实验表明，所提出的模型及设计的动态算法框架能有效解决带时间窗的动态取送货问题（DPDP-TW）.

Dynamic pick-up and delivery problem considering dynamic events in real-world environment

Real-time city distribution strategies are highly dependent on dynamic environments, requiring timely responses to changes of demand and environment due to various dynamic events that take place in the distribution system. A dynamic vehicle routing model based on a dynamic pick-up and delivery problem considering multiple dynamic events in a real-world environment (DPDP-MDE) was established, considering the influence of four kinds of real-time information on vehicle routing and vehicle scheduling, including new requests arriving gradually, old requests being modified or canceled, traffic congestion and vehicle breakdowns. A dynamic algorithm framework is designed to solve this model. The execution rules and calculation rules of static subproblems within scheduled time horizon are given. The constructive heuristic algorithm is used to generate the initial feasible solution for the exact static subproblems. Two intelligent optimization algorithms, tabu search algorithm and adaptive large-scale neighborhood search algorithm, are adopted to improve the quality of those initial feasible solution. The dynamic insertion method is adopted to solve the synchronization problem of unfixed requests and new requests when updating the routing. Experimental results show that the model and dynamic algorithm framework proposed can effectively solve the dynamic pick-up and delivery problem with time windows (DPDP-TW).