Research Article Open Access

Application of Hybrid Encoding Genetic Algorithm on Pickup and Delivery Traveling Salesman Problem with Traffic Conditions

Supat Patvichaichod1
  • 1 , Afganistan
Journal of Computer Science
Volume 7 No. 5, 2011, 605-610

DOI: https://doi.org/10.3844/jcssp.2011.605.610

Submitted On: 16 January 2011 Published On: 7 May 2011

How to Cite: Patvichaichod, S. (2011). Application of Hybrid Encoding Genetic Algorithm on Pickup and Delivery Traveling Salesman Problem with Traffic Conditions. Journal of Computer Science, 7(5), 605-610. https://doi.org/10.3844/jcssp.2011.605.610

Abstract

Problem statement: This study deals with the pickup and delivery traveling salesman problem with traffic conditions (PDTSPTW), an extension of the pickup and delivery traveling salesman problem (PDTSP) where each customer to be served is associated with two quantities of product to be collected and delivered. Almost PDTSP problems uses distance between each point of customers as Euclidean Distance and are not concerned with other parameters to find minimal cost. Approach: The PDTSPTC concerns more parameters, such as street network and vehicle speed, which results it closer to the real world condition. The study also proposes the developed genetic algorithm called “Hybrid Encoding Genetic Algorithm (HEGA)”. The concept is to combine binary encoding and integer encoding together, causing the in complexity of the algorithm structure and the ease of implementation. Results: the HEGA can save the travel cost about 26-57%. It is obviously seen that HEGA in the PDTSPTC test problems result the fast convergence that is about 12-43% and in all, the computational time is under 6 seconds. Conclusion: The HEGA performs quite well when testing a test problem. Computation times are small in all case. The PDTSPTC is closer to real-world conditions than PDTSP. This problem can be applied in logistics immediately if the distance of streets, traffic conditions (average vehicle speed in each street) and vehicle conditions (fuel consumption rate and vehicle capacity) are known.

  • 1,076 Views
  • 1,914 Downloads
  • 0 Citations

Download

Keywords

  • Hybrid encoding
  • genetic algorithm
  • traveling salesman problem
  • Traveling Salesman Problem with Multi-Relations (TSPMR)
  • Pickup and Delivery Traveling Salesman Problem (PDTSP)
  • multiple Traveling Salesperson Problem (m-TSP)
  • traffic conditions
  • vehicle conditions
  • Vehicle Routing Problem (VRP)