Procedia Computer Science

Volume 72, 2015, Pages 503–510

The Third Information Systems International Conference 2015

Edited By Georgeta Bordea

Open Access

Distribution Route Optimization of Gallon Water Using Genetic Algorithm and Tabu Search ☆

  • Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia
Available online 23 December 2015

Abstract

Distributions of drinking water in gallons often do not pay attention to the problem of finding the most optimal route, thus causing inefficiency in the cost of shipping. To minimize incurred costs, it is necessary to minimize vehicle fleet and amount of travel distance, with the restriction that the vehicle must have sufficient capacity to transport the goods to be shipped and return it back to the depots. This problem could be framed as a Vehicle Routing Problem with pick-up and delivery (VRPPD).

In this paper, we propose a method to optimize delivery route in a drinking water depot by combining genetic algorithm (GA) and Tabu search. GA has advantages by providing possible solutions while Tabu covers up its shortfall in identifying local solutions so that searching will able to avoid loop in the area of the same solution. Experimental results show that the proposed method is more efficient than a manually predetermined route.

Keywords

  • vehicle routing problem;
  • pick-up and delivery;
  • gallon water;
  • genetic algorithm;
  • tabu search

References

    • [1]
    • A.S. Tasan, M. Gen

    • A Genetic Algorithm Based Approach to Vehicle Rouing Problem with Simultaneous Pick-up and Deliveries

    • Computer & Industrial Engineering, 62 (2012), pp. 755–761

    • [2]
    • S. Yu, C. Ding, K. Zhu

    • A hybrid GA-TS algorithm for open vehicle routing optimization of coal mines material

    • Expert System with Applications (2011), pp. 10568–10573

    • [3]
    • Chao Ou Yang and Amalia Utamima, “Hybrid Estimation of Distribution Algorithm for solving Single Row Facility Layout Problem,” Computers & Industrial Engineering, 2013.
    • [4]
    • Jairo R. Montoya-Torres, Julián López Franco, Santiago Nieto Isaza, Heriberto Felizzola Jiménez, Nilson Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots”, Computers and Industrial Engineering, p. 115-129, 2015.
    • [5]
    • J. Dethloff, “Vehicle Routing and Reverse Logistics:The Vehicle Routing Problem with Simultaneous delivery and pick-up”, OR Spektrum no. 23, pp. 79-96, 2001.
    • [6]
    • Angelia Melani Adrian, Amalia Utamima, Kung-Jeng Wang, “A comparative study of GA, PSO and ACO for solving construction site layout optimization”, KSCE Journal of Civil Engineering, Volume 19, Issue 3, pp 520-527, March 2015.
    • [7]
    • M. Sheikhalishahi, V. Ebrahimipour, H. Shiri, H. Zaman, M. Jeihoonian, “A hybrid GA–PSO approach for reliability optimization in redundancy allocation problem”, The International Journal of Advanced Manufacturing Technology, Volume 68, Issue 1-4, pp 317-338, 2013.
    • [8]
    • Chaoyong Zhang, Peigen Li, Yunqing Rao, Shuxia Li

    • A New Hybrid GA/SA Algorithm for the Job Shop Scheduling Problem, Evolutionary Computation in Combinatorial Optimization

    • Lecture Notes in Computer Science, 3448 (2005), pp. 246–259

    • [9]
    • F. Glover, “Genetic Algorithms and Tabu Search: Hybrids for Optimization,” Computer and Operation Research, pp. 111-134, 1995.
    • [10]
    • R. Thamilselvan, P. Balasubramanie

    • A Genetic Algorithm with a Tabu Search (GTA) for Traveling Salesman Problem

    • International Journal of Recent Trends in Engineering (2009), pp. 607–610

    • [11]
    • http://w.cba.neu.edu/∼msolomon/problems.htm, accessed in April 2015.
☆

Peer-review under responsibility of organizing committee of Information Systems International Conference (ISICO2015).

Corresponding author. Tel.: +62 31 5999944.

Copyright © 2015 Published by Elsevier B.V.