Novel Formulations and Improved Differential Evolution Algorithm for Optimal Lane Reservation With Task Merging

This paper investigates a new lane reservation problem with task merging that consists of optimally determining which lanes in a transportation network have to be reserved and designing reserved lane-based routes in the network for time-crucial transport tasks. Part of the tasks whose destinations are geographically close is merged to reduce the number of vehicles and transport costs. Reserved lanes can reduce the travel time of task vehicles passing through them, while they will generate negative impact on normal traffic, such as traffic delay to the vehicles on adjacent non-reserved lanes. The objective is to minimize the total negative impact of all reserved lanes. For this problem, two new integer linear programming (ILP) models are first developed. The complexity of the problem is proved to be NP-hard. Since commercial solver (like CPLEX) is time-consuming for solving it when the problem size increases, a fast and effective improved differential evolution algorithm (IDEA) is developed based on explored problem properties. Extensive experimental results for a real-life case and benchmark instances of up to 500 nodes in the network and 30 transport tasks show the favorable performance of the IDEA, as compared to CPLEX, differential evolution algorithm and genetic algorithm. Management insights are also drawn to support practical decision-making.