基于Benders分解的租赁车队规划

Fleet Scheduling in the Car Rental Industry Based on Benders Decomposition

以汽车租赁业的日常车辆调配为背景,研究租赁车队的战术规划问题。将车辆调配情况抽象到时空网络结构中,并根据车辆需求的供应策略和时空节点的流量平衡得到约束条件,以企业运营成本最小为目标建立优化模型。针对模型特点采用Benders分解算法将原问题分解为两类子问题,给出对应的算法步骤。以一周为战术规划期设计算例,对模型和算法的有效性进行检验,结果表明能够为优化车队调配提供较好的辅助决策支持。

With the daily car deployment in car rental industry as background for this work,the fleet scheduling problem is addressed in this paper.The car deployment among rental locations is formulated as a time-space network.With this formulation,constraints for this scheduling problem are obtained according to the supply policy and flow balance at each node.After analyzing the characteristics of the model,the problem was decomposed into two sub-problems by using Benders decomposition,and a solution algorithm is proposed.A numerical example with a one-week scheduling horizon is given to demonstrate the effectiveness of the proposed method.Results show that it works well.