论文标题
关于电动汽车共享问题的复杂性和建模
On the complexity and modeling of the electric vehicle sharing problem
论文作者
论文摘要
我们引入了电动汽车共享问题（EVSP），这是由电动汽车共享系统的计划和操作引起的，该系统允许单向租赁车辆。该问题旨在找到将客户需求分配给现有车队的最长每日租赁时间。此外，要么所有客户的需求都是完全满足的，要么客户根本不使用该系统。我们证明了EVSP是NP-HARD，并且我们提供了基于时空网络流模型的四个混合成员线性编程公式以及一些理论结果。我们使用两个基准组对拟议配方的行为进行了全面的计算研究，其中一个基于位于巴西福特莱萨的电动汽车共享系统的实际数据。结果表明，我们最好的配方在解决每个客户只有一个需求的情况下有效。通常，我们能够在一小时的时间限制内最佳地解决至少55％的实例。
We introduce the electric vehicle sharing problem (EVSP), a problem that arises from the planning and operation of electric car-sharing systems which allow one-way rental of vehicles. The problem aims at finding the maximum total daily rental time in which customers' demands are assigned to the existing fleet. In addition, either all of the customer's demands are completely fulfilled or the customer does not use the system at all. We show that the EVSP is NP-hard, and we provide four mixed-integer linear programming formulations based on space-time network flow models, along with some theoretical results. We perform a comprehensive computational study of the behavior of the proposed formulations using two benchmark sets, one of which is based on real-world data from an electric car-sharing system located in Fortaleza, Brazil. The results show that our best formulation is effective in solving instances where each customer has only one demand. In general, we were able to optimally solve at least 55% of the instances within the time limit of one hour.
