Vehicle Routing Problems: Decision Support Systems and Distributed Approaches

Modern logistics received increasing attention for planning and scheduling operations of transport systems that have to be resource efficient, environmentally sustainable, and compatible with workers’ rights. In particular, modern timeliness requirements and technological advances respectively call for and enable new formulations and solutions for the classical vehicle routing problem (VRP). Indeed, companies and service supplier need of real-time data and fast procedure to face uncertainty and meet people’s expectative, and Information Communication Technologies make this information increasingly available. In other word, some topics emerge: dynamic VRP (DVRP), need of decision support systems (DSS), distributed approaches, balancing workloads for drivers. Firstly, the thesis exposes a review of recent contributions about DVRP, enlightening classifications by source of dynamism (factor of uncertainty), applications, methodologies. A particular attention is paid to distributed approaches, which still represent a minority part of literature. Secondly, due to the complexity and the urgency character of real-world application, the thesis proposes an architecture for a Decision Support System (DSS) that includes a fast VRP module devoted to critical services in city logistics, such as waste collection. The module can be fed with data that are tailored on different scenarios and can be customized for different logistics services. The core of the module is a two-phase heuristic algorithm able to solve a VRP with work shifts constraints for a waste collection service involving large network of pick-up locations. The algorithm is assessed by comparisons with Mixed Integer Linear Problems (MILP) and by the application to real case studies. Thirdly, the thesis proposes a distributed approach for VRP with time windows constraints (VRPTW) in a static and dynamic setting, which also takes in account workload balancing. In particular, the distributed approach is applied to a VRPTW and a multi-depot VRPTW (MDVRPTW), which can respectively act as the initial component and the ongoing component of a DVRP, in which the source of dynamism is the arrival of new service requests. The general strategy is the "cluster first, route second" and the core of the approach consists of an asynchronous, randomized and distributed algorithm. More precisely, vehicles reach the final assignment by iteratively solving local Graph Partitioning problems, in the form of Local-Integer Linear Programming problems (L-ILP), with randomly selected neighbor agents. Afterwards, each vehicle can optimize the route into its own cluster, by solving a small instance of the Traveling Salesman Problem with Time Windows. The proposed approach is assessed for both VRPTW and MDVRPTW by comparisons with exact and centralized approaches with particular regard to balanced workloads in terms of average traveling times, average vehicle loads and their standard deviations. Moreover, an example inspired by a transport company shows the applicability of the proposed approach in real-world scenarios.