Heuristic approaches for vehicle routing problem with simultaneous pickup and delivery: Genetic algorithm and particle swarm optimization

In today?s competitive environment, it is obvious that companies should makestrategic and operational decisions in order to optimize and manage theprocesses in their supply chain more efficiently. One of the most importantoperational decisions concerns to determine of vehicle routes. Classical vehiclerouting problem can be defined as the problem of designing optimal delivery orpickup routes from one depot to a number of customers. Different variants ofvehicle routing problem depending on some restrictions, which are faced in thepractice, have been proposed in the literature. One of these variants is theVehicle Routing Problem with Simultaneous Pickup and Delivery (VRP_SPD).In the VRP_SPD, pickup and delivery demands of customers in each route aremet simultaneously. Since the VRP_SPD is an NP-hard problem, differentheuristic solution algorithms have been proposed to solve the problem in theliterature. In this thesis, two hybrid algorithms based on Genetic Algorithm(GA), Particle Swarm Optimization (PSO) and Variable Neighborhood Descent(VND) algorithm called GA_VND and PSO_VND are developed. While GA andPSO are used to explore solution space of the problem, VND is implemented tointensify around one or several good solutions found during search process ofthe hybrid algorithms. An experimental study is carried out to investigate theperformances of GA_VND and PSO_VND. The computational results over 76test instances indicate that the proposed hybrid algorithms compete with theheuristic approaches, which are proposed in the literature for the VRP_SPD, interms of solution quality and also GA_VND improves known best solution forsome instances.