A Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery Using Depot Removal and Insertion Moves

Date

2010-04-09

Author

Cinar, Volkan
ÖNCAN, TEMEL
Süral, Haldun

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

100
views

0
downloads

In this work, we consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), which is an extension of the well-known NP-hard Traveling Salesman Problem. We propose a Genetic Algorithm (GA) based on a specially tailored tour improvement procedure for the TSPPD. Computational experiments are reported on the test instances taken from the literature. The experimental results suggest that the proposed GA yields a promising performance in terms of both accuracy and efficiency compared to existing algorithms in the literature.

Subject Keywords

Genetic algorithm, Traveling salesman problem, Pickup and delivery

URI

https://hdl.handle.net/11511/53817

Collections

Department of Industrial Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

An evolutionary approach to generalized biobjective traveling salesperson problem Köksalan, Mustafa Murat; Ozturk, Diclehan Tezcaner (2017-03-01) We consider the generalized biobjective traveling salesperson problem, where there are a number of nodes to be visited and each node pair is connected by a set of edges. The final route requires finding the order in which the nodes are visited (tours) and finding edges to follow between the consecutive nodes of the tour. We exploit the characteristics of the problem to develop an evolutionary algorithm for generating an approxiMation of nondominated points. For this, we approximate the efficient tours using...
A genetic algorithm for the uncapacitated single allocation planar hub location problem Damgacioglu, Haluk; DİNLER, DERYA; Özdemirel, Nur Evin; İyigün, Cem (2015-10-01) Given a set of n interacting points in a network, the hub location problem determines location of the hubs (transfer points) and assigns spokes (origin and destination points) to hubs so as to minimize the total transportation cost. In this study, we deal with the uncapacitated single allocation planar hub location problem (PHLP). In this problem, all flow between pairs of spokes goes through hubs, capacities of hubs are infinite, they can be located anywhere on the plane and are fully connected, and each s...
A genetic algorithm for TSP with backhauls based on conventional heuristics Önder, İlter; Özdemirel, Nur Evin; Department of Information Systems (2007) A genetic algorithm using conventional heuristics as operators is considered in this study for the traveling salesman problem with backhauls (TSPB). Properties of a crossover operator (Nearest Neighbor Crossover, NNX) based on the nearest neighbor heuristic and the idea of using more than two parents are investigated in a series of experiments. Different parent selection and replacement strategies and generation of multiple children are tried as well. Conventional improvement heuristics are also used as mut...
A column generation approach for the location-routing problem with time windows Farham, Mohammad Saleh; Süral, Haldun; İyigün, Cem (2018-02-01) The location-routing problem with time windows consists of opening a subset of depots, assigning customers to depots, and determining routes within allowable times such that the sum of depot opening, vehicle usage, and traveling costs is minimized. Customers have to be visited only once during their time windows and depot capacities and load limits of vehicles cannot be violated. In order to find the exact solution to the problem, we propose a branch-and-price algorithm based on set-partitioning approach. T...
A Branch-and-bound algorithm for airport gate assignment problem Alanlı, Kerem; Azizoğlu, Meral; Department of Industrial Engineering (2019) In this study, we consider an airport gate assignment problem that assigns a number of aircraft to a set of gates so as to minimize total walking distance travelled by all passengers. The aircraft that cannot be assigned to any gate due to overlaps are directed to an apron. The problem is formulated as a mixed-integer nonlinear programming model and then it is linearized. A branch-and-bound algorithm that employs powerful bounding mechanisms is developed. The results of the computational experiment have sho...

Citation Formats

V. Cinar, T. ÖNCAN, and H. Süral, “A Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery Using Depot Removal and Insertion Moves,” 2010, vol. 6025, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/53817.