The generalized one-to-one pickup and delivery vehicle routing problem and solution methods

The Vehicle Routing Problem (VRP), one of the most important problems in the logistics industry, aims to find the most suitable routes for vehicles that meet the demands of customers. Many studies on VRP are presented in favor of this purpose, and solution approaches are obtained. VRP is examined under various variants, and one of these variants, the Pickup and Delivery Vehicle Routing Problem (PDVRP), deals with the pickup demands as well as the delivery demands of the customers. This problem is divided into three main categories according to demand type and route structure: one-to-many-to-one problems, many-to-many problems, and one-to-one problems. In one-to-many-to-one problems, there are goods at the depot to be delivered to customers as well as goods at customers to be carried back to the depot. In many-to-many problems, one node can be the origin or destination point for a good, and multiple nodes can be the origin or destination point for each good, while in one-to-one problems, there is a single origin and a single destination point for each unique demand. Within the scope of this thesis, a literature review is presented on the PDVRP. Then a problem that can be classified as one-to-one problems, has a practical equivalent, and has not been addressed in literature so far, is defined. A mathematical model is developed for the solution of the problem, and the model is improved using valid inequalities to improve the performance. Experimental studies are performed with GAMS/CPLEX on 270 randomly generated test instances. Since PDVRP is an NP-Hard problem like classical VRP, the mathematical model provides optimal solutions only for small-sized instances.