A Distributed Cluster-Based Approach for Pick-Up Services

作     者：Abbatecola, Lorenzo Fanti, Maria Pia Pedroncelli, Giovanni Ukovich, Walter 

作者机构：Univ Trieste Dept Engn & Architecture I-34127 Trieste Italy Polytech Univ Bari Dept Elect & Informat Engn I-70126 Bari Italy 

出 版 物：《IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING》 (IEEE自动化科学与工程学汇刊)

年 卷 期：2019年第16卷第2期

页      面：960-971页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 

基　　金：European Union H2020 Societal Challenges Programme Funding Source: H2020 Societal Challenges Programme 

主　　题：Distributed algorithms logistics vehicle routing problem (VRP) 

摘      要：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.