This study focuses on two types of routing problems based on standard Traveling Salesman Problem, which are TSP with pickup and delivery (TSPPD) and TSP with backhauls (TSPB). In both of these problems, there are two types of customers, i.e. &ldquo / delivery customers&rdquo / demanding goods from depot and &ldquo / pickup customers&rdquo / sending goods to depot. The objective is to minimize the cost of the tour that visits every customer once without violating the side constraints. In TSPB, delivery customers should precede the pickup customers, whereas the vehicle capacity should not be exceeded in TSPPD.
The aim of the study is to propose good Evolutionary Algorithms (EA) for these two problems and also analyze the adaptability of an EA, originally designed for the standard TSP, to the problems with side constraints. This effort includes commenting on the importance of feasibility of the solutions in the population with respect to these side constraints. Having this in mind, different EA strategies involving feasible or infeasible solutions are designed. These strategies are compared by quantitative experiments realized over a set of problem instances and the results are given.
Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12605083/index.pdf |
Date | 01 June 2004 |
Creators | Demir, Erdem |
Contributors | Sural, Haldun |
Publisher | METU |
Source Sets | Middle East Technical Univ. |
Language | English |
Detected Language | English |
Type | M.S. Thesis |
Format | text/pdf |
Rights | To liberate the content for public access |
Page generated in 0.0017 seconds