灵活多车场多类型的叫车接送问题的规划模型

A Programming Model for the Flexible Multi-depot Heterogeneous Dial-a-ride Problems

为解决1种新的叫车接送问题(DARP)——灵活多车场多类型的叫车接送问题(MDHDARP-FD),建立以总行驶成本最小为目标的混合整数非线性规划数学模型。由于模型非常复杂,难以直接求解,对模型进行约束线性化、变量聚合和添加有效不等式等处理。在约束线性化过程中,非线性约束被重写为等价的线性约束;在变量聚合过程中,将具有相同性质的决策变量进行聚合,以减少变量数量;还引入了一些有效不等式来强化模型。从而获得1个解空间较小易于求解的新线性规划模型,并结合不同类型的车辆和乘客需求进行叫车接送问题的仿真测试。算例结果表明,相比于传统叫车接送问题,该模型能在满足复杂约束的基础上,得到1组实现乘客接送需求的最优车辆路线,并且能有效降低总行驶成本、车辆行驶时间和求解时间,总行驶成本在不同类型的DARP上可平均降低1.51%~6.69%,证实了叫车接送问题的总行驶成本可以随着灵活车场的引入而减少。

A mathematical model of mixed-integer non-linear programming is firstly constructed to solve a new dial-a-ride problem(DARP),the multi-depot heterogeneous dial-a-ride problem with flexible depots(MDHDARP-FD),as well as minimize the total driving cost.Due to the complexity of the proposed model,some strategies of linearizing constraints,aggregating variables,and strengthening inequalities are performed to reformulate the non-linear model.During linearizing constraints,non-linear constraints are rewritten as equivalent linear constraints.Aggregating variables,decision variables with the same properties,are aggregated to reduce the number of variables,with strengthened inequalities and valid inequalities introduced to strengthen the model.As a result,a new linear programming model with a small solution space is obtained and can be tractable.Then the dial-a-ride problem is simulated by combining different vehicles and passengers’demands.Simulation results show that compared with the traditional dial-a-ride problems,the model can obtain a group of optimal vehicle routes respecting the complex constraints and reduce the total driving cost,vehicle driving time,and solution time.The total driving cost can be reduced by1.51%to6.69%for different DARPs on an average,verifying that the total driving cost of dial-a-ride problems can be reduced with the introduced flexible depots.