Solving Rich Vehicle Routing Problem Using Three Steps Heuristic
DOI:
Abstract
Vehicle Routing Problem (VRP) relates to the problem of providing optimum service with a fleet of vehicles to customers. It is a combinatorial optimization problem. The objective is usually to maximize the profit of the operation. However, for public transportation owned and operated by government, accessibility takes priority over profitability. Accessibility usually reduces profit, while increasing profit tends to reduce accessibility. In this research, we look at how accessibility can be increased without penalizing the profitability. This requires the determination of routes with minimum fuel consumption, maximum number of ports of call and maximum load factor satisfying a number of pre-determined constraints: hard and soft constraints. To solve this problem, we propose a heuristic algorithm. The results from this experiment show that the algorithm proposed has better performance compared to the partitioning set.
Downloads
Views : 451
Downloads : 346
References
G. B. Dantzig and J. H. Ramser, “The truck dispatching problem, Management Science”, vol. 6, no. 1, pp. 80-91, 1959.
E. Falkenauer, “A hybrid grouping genetic algorithm for bin packing”, Journal of Heuristics, vol. 2, no.1, pp. 5-30, 1996.
F. Greco and I. Gerace, “The symmetric circulant traveling salesman problem”, in F. Greco (Ed.) Travelling Salesman Problem, I-Tech, Vienna, Austria, pp. 202, 2008.
J. -D. Wei, “Approaches to the travelling salesman problem using evolutionary computing algorithms” in F. Greco (Ed.) Travelling Salesman Problem, I-Tech, Vienna, Austria, pp. 202, 2008.
M. R. Bonyadi, M. R. Azghadi, and H. S. Hosseini, “Population-based optimization algorithms for solving the travelling salesman problem”, in F. Greco (Ed.) Travelling Salesman Problem, I-Tech, Vienna, Austria, pp. 202-236, 2008.
Y. H. Liu, “Solving the probabilistic travelling salesman problem based on genetic algorithm with queen selection scheme”, in F. Greco (Ed.) Travelling Salesman Problem, I-Tech, Vienna, Austria, pp. 202, 2008.
L. Lupsa, I. Chiorean, R. Lupsa and L. Neamtiu, “Some special traveling salesman problems with applications in health economics”, in D. Davendra (Ed.) Traveling Salesman Problem, Theory and Applications, InTech, pp. 298, 2010.
R. Matai, S.P. Singh, and M. L. Mittal, “Traveling salesman problem: an overview of applications, formulations, and solution approaches”, in D. Davendra (Ed.) Traveling Salesman Problem, Theory and Applications, InTech, pp. 298, 2010.
H. C. W. Lau, T. M. Chan, W. T. Tsui, and W.K. Pang, “Application of genetic algorithms to solve the multidepot vehicle routing problem”, IEEE Transactions on Automation Science and Engineering, vol. 7, no. 2, pp. 383-392, 2010.
S. Salhi and M. Sari, “A multi-level composite heuristic for the multi-depot vehicle fleet mix problem”, European Journal of Operational Research, vol. 103, no. 1, pp. 95-112, 1997.
G. Nagy and S. D. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries”, European Journal of Operational Research, vol. 162, no. 1, pp. 126-141, 2005.
J. Renaud, G. Laporte, and F. F. Boctor, “A Tabu Search heuristic for the multi-depot vehicle routing problem,” Computers & Operations Research, vol. 23, no. 3, pp. 229-235, 1996.
J. F. Cordeau, M. Gendreau, and G. Laporte, “A Tabu Search heuristic for periodic and multi-depot vehicle routing problems,” Networks, vol. 30, no. 2, pp. 105-119, 1997.
M. Skok, D. Skrlec and S. Krajcar, “The genetic algorithm method for multiple depot capacitated vehicle routing problem solving”, in Proceedings Knowledge-Based Intelligent Engineering Systems and Allied Technologies, Fourth International Conference, pp. 520-526, 2000.
G. Jeon, H. R. Leep, J. Y. Shim, “A vehicle routing problem solved by using a hybrid genetic algorithm,” Computers & Industrial Engineering, vol. 53, no. 4, pp. 680-692, 2007.
E. D. Taillard, “A heuristic column generation method for the heterogeneous fleet VRP,” RAIRO - Operations Research, vol. 33, no. 1, pp. 1-14, 1999.
C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, “A list-based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem,” Journal of the Operational Research Society, vol. 54, no. 1, pp. 65-71, 2003.
C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem”, Journal of the Operational Research Society , vol. 152, pp. 148-158, 2004.
H. Yaman, “Formulations and valid inequalities for the heterogeneous vehicle routing problem,” Mathematical Programming, vol. 106, no. 2, pp. 365-390, 2006.
E. Choi, and D. W. Tcha, “Column generation approach to the heterogeneous fleet vehicle routing problem,” Computers & Operations Research, vol. 34, no. 7, pp. 2080-2095, 2007.
A. Pessoa, E. Uchoa, and M. P. D. Aragão, “A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem,” Networks, vol. 54, no. 4, pp. 167-177, 2009.
M. Gendreau, G. Laporte, C. Musaraganyi, and E.D. Taillard, “A tabu search heuristic for the heterogeneous fleet vehicle routing problem,” Computers & Operations Research, vol. 26, pp. 1153-1173, 1999.
C. Prins, “Eficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case,” Journal of Mathematical Modelling and Algorithms, vol. 1, no. 2, pp. 135-150, 2002.
R. Dondo, and J. Cerdá, “A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows,” European Journal of Operational Research, vol. 176, no. 3, pp. 1478-1507, 2007.
P. H. V. Penna, A. Subramanian, and L. S. Ochi, “An iterated local search heuristic for the heterogeneous fleet vehicle routing problem,” Journal of Heuristics, pp. 1-32, 2011.
A. Subramanian, P.H.V. Penna, E. Uchoa, and L.S. Ochi, “A hybrid algorithm for the heterogeneous fleet vehicle routing problem,” European Journal of Operational Research, vol. 221, pp. 285-295, 2012.
L. S. Ochi, D. S. Vianna, L. Drummond, and A. Victor, “A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet,” Future Generation Computation Systems, vol. 14, no. 5, pp. 285-292, 1998.
F. Li, B. Golden, and E. Wasil, “A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problems,” Computers & Operations Research, vol. 34, no. 9, pp. 2734-2742, 2007.
C. Prins, “Two memetic algorithms for heterogeonous fleet vehicle routing problems,” Engineering Applications of Artificial Intelligence, vol. 22, no. 6, pp. 916-928. (2009).
I. M. Chao, T. S. Liou, “A new tabu search heuristic for the site dependent Vehicle routing problem,” In the Next Wave in Computing, Optimization, and Decision Technologies, pp. 107-119, 2005.
I.M. Chao, B. Golden, and E. Wasil, “A computational study of a new heuristic for the site-dependent vehicle routing problem,” INFOR, vol. 37, no. 3, pp. 319-336, 1999.
C. Archetti, D. Feillet, M. Gendreau, and M. Speranza, “Complexity of the VRP and SDVRP,” Transportation Part C, pp. 1-10, 2010.
J.F. Cordeau, and G. Laporte, “A Tabu Search algorithm for the site dependent vehicle routing problem with time windows,” INFOR, vol. 39, no. 3, pp. 292-298, 2011.
Choi, I.-C., Kim, S. I., & Kim, H.-S, A genetic algorithm with a mixed region search for the asymmetric travelling salesman problem,” Computers & Operations Research, vol. 30, no. 5, pp. 773-786, 2003.
S. Basu, R. S. Gajulapalli and D. Ghosh, “Implementing tabu search to exploit sparsity in ATSP instances”, in Indian Institute of Management, 2008.
X. Hao, “A Fuel Consumption Objective of VRP and the Genetic Algorithm”, in Proceedings E-Product E-Service and E-Entertainment (ICEEE), pp. 1-4, 2010.
Y. Kuo, “Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem,” Computers & Industrial Engineering, vol. 59, pp. 157-165, 2010.
R. L. Bowerman and P. H. Calamai, “The spacefilling curve with optimal partitioning heuristic for the vehicle routing problem,” European Journal of Operational Research, vol. 76, no. 1, pp. 128–142, 1994.
C. Novoa, R. Berger, J. Linderoth, and R. Storer, “A set-partitioning-based model for the stochastic vehicle routing problem,” in Lehigh University, pp. 1-30, 2006.
I. Pertiwi, “Pendekatan pemecahan berbasis set covering heuristik untuk pemecahan masalah penentuan rute dan penugasan kapal,” in Institute of Technology Bandung, Bandung, Indonesia”, 2005.
D. E. Goldberg, “Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Professional”, 1989.
P. M Nasional, “Panduan Pelayanan BBM Bunker,” in Direktorat Pemasaran dan Niaga, 2008.
