Toplamalı dağıtımlı gezgin satıcı problemi için depo yerleştirme ve çıkarma tabanlı bir sezgisel algoritma

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is an extension ofthe famous Traveling Salesman Problem (TSP). In the literature there are many problemsrelated to pickup and delivery but they have different features (i.e. single commodity ormulti commodities, single vehicle or multi vehicles, one-to-one or one-to-many etc.).TSPPD is a static simultaneous pickup delivery problem with a ?one-to-many-to-one?structure where there is only one vehicle and that each customer is visited exactly once.The problem involves two sets of customers. ?Delivery Customers? are served bydelivery of the goods from a central warehouse. ?Pickup Customers? need to delivergoods from their locations to the central warehouse. We call the central warehouse as?Depot? and all delivery and pickup services are done by a single vehicle with a givencapacity which is equal to Q. Given two types of goods (delivery and pickup goods), avehicle which departs from the depot with fully loaded satisfies all the customer?s needsand returns back to the depot. The objective of the TSPPD is to minimize the totaltravelling distance. The additional constraint of the TSPPD is that the vehicle load mustbe feasible throughout the tour; it must remain nonnegative and the total load should notexceed the vehicle capacity. TSPPD is an NP-hard combinatorial optimization problemsince it as an extension of the well known TSP. To the best of our knowledge there is notmany publications on the TSPPD. The motivation of this thesis is to propose an efficientGenetic Algorithm (GA) to solve TSPPD instances.GAs are search algorithms based on the mechanics of natural selection and naturalgenetics. The basic principle of the GAs comes from ?survival of the fittest? which isstated by Charles Darwin in ?The Origins of Species?. They are adaptive methods whichmay be used to solve search and optimization problems. The power of GA comes fromthe fact that the method is robust and which can be used successfully for a wide range ofproblem areas including those which are difficult for other methods to solve.The motivation behind of the proposed GA, lies in the Mosheiov Theorem. Mosheiov hasproved that when we construct a Hamiltonian tour covering all pickup and deliverycustomers without the depot, there exists at least one point ik on this tour such that whenwe insert the depot between ik and ik+1 the resulting tour is feasible. Considering thistheorem we have devised an efficient algorithm which consists of three steps. The firststep is to solve Hamiltonian tour through all customers by using the GA. The second stepis to find the best starting point to insert the depot. The final step is to apply a localneighborhood search which we term as ?Tuning Phase?. Computational experiments arereported on standard test instances from the literature. The experimental results show thatour algorithm yields promising performance in terms of both accuracy and efficiencycompared to existing algorithms in the literature. We should also report that the tuningphase step considerably improves the solution obtained after the second step. This showsus the power of our tour improvement procedure, which is specially designed for theTSPPD.