计算机科学
列生成
数学优化
车辆路径问题
解算器
稳健优化
运筹学
布线(电子设计自动化)
工程类
数学
计算机网络
作者
Xiaochang Liu,Dujuan Wang,Yunqiang Yin,T.C.E. Cheng
标识
DOI:10.1016/j.cor.2022.106119
摘要
Recently, electric vehicles have become a viable option for city logistics to reduce air pollution and operating noise. In this study we consider the pickup and delivery problem with time windows involving battery-powered electric vehicles under demand uncertainly, where the uncertain demands fall within a budget polytope uncertainty set. We develop a two-stage adaptive robust model to find solutions that are insusceptible to a certain number of deviations in demands, where the routing, and the service start times and remaining battery capacities along a route are fixed before the realization of uncertain demands, while the quantities to load and unload along the route are adjustable to the demand scenario. To solve the model, we develop an exact two-phase decomposition method based on column-and-row generation to alleviate the computational difficulty arising from the large number of demand scenario-related variables and constraints, which decomposes the robust model into a master problem comprising only partial demand scenario-related variables and constraints, and an adversarial separation problem that verifies whether there are infeasible demand scenarios for the solution to the master problem. We develop a tailored branch-and-price-and-cut algorithm incorporating various acceleration strategies to solve the master problem, and a dynamic programming algorithm to solve the adversarial separation problem. We also conduct extensive numerical studies to evaluate the performance of the developed algorithm, ascertain the benefits of the robust model over the deterministic model, and analyze the effect of the charge consumption rate of the battery on the optimal solution.
科研通智能强力驱动
Strongly Powered by AbleSci AI