.png){kind=icon}
返回
An exact algorithm for simultaneous pickup and delivery problem with split demand and time windows
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2024.106761.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This study introduces a new variant of the vehicle routing problem (VRP) called the simultaneous pickup and delivery problem with split demand and time windows (SPDP-SDTW). The motivation behind this study stems from real-life urban and rural delivery scenarios, encompassing features such as split demand, simultaneous pickup and delivery, many-to-many pickup and delivery, and time windows. The study thoroughly investigates the properties of the optimal solution for the SPDP-SDTW. Based on these properties, an arc flow model is developed for the SPDP-SDTW. Dantzig Wolfe (DW) decomposition techniques are employed to obtain the master problem and the pricing subproblem. In order to effectively address the SPDP-SDTW, an improved branch and price (I-BP) algorithm is proposed, incorporating a tailored column generation (CG) algorithm, branching strategies, and dual stabilization strategies. The proposed CG algorithm provides a framework that combines the improved adaptive degree heuristic (I-AGH) algorithm and the solver Gurobi. This integration substantially mitigates the computational burden involved in solving the subproblem. Extensive computational experiments conducted on datasets of varying sizes, including small, medium, and large instances, consistently demonstrate that the I-BP algorithm performs the best in both solution quality and computational efficiency when compared to existing exact and heuristic algorithms.
Keyword:
Vehicle routing problem with time windows
Split demand
Simultaneous pickup and delivery
Urban and rural distribution
Branch and price
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
分享收藏分享收藏Branch and price for the vehicle routing problem with discrete split deliveries and time windows具有离散分割交货和时间窗的车辆路径问题的分支和价格
OAAI
OAAI分享收藏Prevalence of Inflammatory Bowel Disease and Celiac Disease in Patients with IgA Nephropathy over Time.png)
Nephron
NephronIF0
PREAI
分享收藏
A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickupsOAAI
OAAI分享收藏
查看更多内容