Journal
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
Volume 16, Issue 2, Pages 960-971Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TASE.2018.2879875
Keywords
Distributed algorithms; logistics; vehicle routing problem (VRP)
Categories
Funding
- European Union [690797]
- H2020 Societal Challenges Programme [690797] Funding Source: H2020 Societal Challenges Programme
Ask authors/readers for more resources
This paper deals with the routing problem of pick-up and delivery services considering time windows and capacitated vehicles. In order to consider large real problems, this paper proposes a distributed vehicle routing problem (VRP) with time windows, based on cluster first, route second methods. First, by using a graph partitioning solved by local integer linear programing problems, the vehicles autonomously generate a number of clusters equal to the number of available vehicles. Second, each vehicle solves a traveling salesman problem with time windows to compute its route in the assigned cluster. The method can be applied by the vehicles for both planning the workday of the pick-up services and adapting the routing plan to manage the ongoing requests. Some benchmark problems are generated and solved by the distributed algorithm and compared with the solution obtained by the exact approach. Moreover, a real case study involving a courier service shows the efficiency of the solution method. Note to Practitioners-The motivation of this paper is to propose a distributed heuristic method for solving real pick-up service problems in static and dynamic settings. The proposed approach provides solutions with twofold key features. First, the distributed and iterative algorithm of the proposed method enables vehicles to compute routes that are characterized by balanced workloads for the drivers. Second, the method is applicable to plan the daily workload of vehicles and to dynamically adapt the routing plan for servicing the ongoing requests. Future research aims at extending the method to other variants of VRPs and at including the solver into a decision support system, with a suitable use of the modern information and communication technologies.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available