Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints

Abstract

We investigate a kind of vehicle routing problem with constraints (VRPC) in the car-sharing mobility environment, where the problem is based on user orders, and each order has a reservation time limit and two location point transitions, origin and destination. It is a typical extended vehicle routing problem (VRP) with both time and space constraints. We consider the VRPC problem characteristics and establish a vehicle scheduling model to minimize operating costs and maximize user (or passenger) experience. To solve the scheduling model more accurately, a spatiotemporal distance representation function is defined based on the temporal and spatial properties of the customer, and a spatiotemporal distance embedded hybrid ant colony algorithm (HACA-ST) is proposed. The algorithm can be divided into two stages. First, through spatiotemporal clustering, the spatiotemporal distance between users is the main measure used to classify customers in categories, which helps provide heuristic information for problem solving. Second, an improved ant colony algorithm (ACO) is proposed to optimize the solution by combining a labor division strategy and the spatiotemporal distance function to obtain the final scheduling route. Computational analysis is carried out based on existing data sets and simulated urban instances. Compared with other heuristic algorithms, HACA-ST reduces the length of the shortest route by 2%–14% in benchmark instances. In VRPC testing instances, concerning the combined cost, HACA-ST has competitive cost compared to existing VRP-related algorithms. Finally, we provide two actual urban scenarios to further verify the effectiveness of the proposed algorithm.

Keywords

Vehicle routing problem with constraints (VRPC) / Spatiotemporal distance function / Labor division strategy / Ant colony algorithm (ACO)

RIGHTS & PERMISSIONS

Zhejiang University Press