The split-demand one-commodity pickup-and-delivery travelling salesman problem

Abstract

This thesis focuses on a kind of problems thoroughly studied in operational research, in particular in Vehicle Routing Problems. Despite there are a lot of studies about them, the most basic are still difficult to solve optimally, even for small size and the lacking practical use. Because of that, this thesis develops exact and heuristic algorithms to solve a particular problem known as The split-demand one-commodity pickup-and-delivery travelling salesman problem (SD1PDTSP). This combines three vehicle routing problems. The first one is the Capacitated Vehicle Routing Problem (CVRP), aiming at designing the routes for a vehicle fleet to deliver a commodity from the depot to a set of customers. Each route starts and ends at the depot, and the load of a vehicle through a route should never exceed the vehicle capacity. A fundamental assumption is that each customer cannot be visited more than once. The aim of the CVRP is to satisfy the demand of each customer while minimizing the total distance travelled by the fleet. The second problem is the Split Delivery Vehicle Routing Problem (SDVRP), which allows a customer to be visited more than once. The third problem still moves one commodity while it allows more than one pickup location. It is the One Commodity Pickup-and-Delivery Travelling Salesman Problem (1-PDTSP). Using the elements of these three problems, the SD1PDTSP is defined as follows. Let us consider a finite set of locations. The travel distances (or costs) between the locations are assumed to be known. Each location is related to a customer, with a known positive or negative demand of a commodity (e.g. bicycles). We assume that the sum of all demands is equal to zero. Customers with negative demands correspond to pickup locations, and customers with positive demands correspond to delivery locations. It is assumed that there is one vehicle with a given capacity that must visit each location at least once through a route to move the commodity and satisfy all the customer demands. Each visit may partially satisfy a customer, and all the visits to that customer must end up with exactly its full demand. The SD1PDTSP consists of finding a minimum-cost route for the vehicle such that it satisfies the demand of all customers. Note that such a route may not exist, and in general checking whether a feasible solution exists is a NP-complete problem due to the limitation in the number of visits to each location and the vehicle capacity. The importance of these kind of problems is not due to the computational complexity only, but also the variety of practical applications. In fact, the idea of Operational Research appears formally in 1938 in the SecondWorldWar, in the frame in collaborative researches between soldiers and scientists about planning of fight military operations. A part of the most obvious examples in logistic (distribution of commodities, scholar routes,etc.), there are more examples as operational control of traffic light, those that can be found in robotic systems that allow to solve production problems, in genetic, etc. Other kind of practical applications arise due to the growing worry about environment. This thesis studies the case of the management of bicycle sharing systems. These are increasingly in demand due to the need of space, the high traffic density and the high emission of noise and CO2.