An Efficient Genetic Algorithm for a Vehicle Routing Problem Considering the Competency of Working Teams

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Mazandaran University of Science and Technology, Iran

2 School of Industrial Engineering and Engineering Optimization Research Group, College of Engineering, University of Tehran, Iran

Abstract

This paper presents a new mathematical model for a combined manpower vehicle routing problem, in which working teams are considered as servers. Having teams with different competency affects the service duration and cost that expands the flexibility of scheduling. A fleet of vehicles with different speed and cost of movement is used to transport these teams to visit the customers before the due date. The goal is to find an efficient schedule for the teams and vehicles movement to serve all the customers in order to minimize the total cost of serving, routing and lateness penalties. A mixed-integer programming model is presented and a number of tests problems are generated. To solve the large-sized problems, two meta-heuristics approaches, namely genetic algorithm (GA) and particle swarm optimization (PSO) are developed, and then the Taguchi experimental design method is applied to set the proper values of the parameters. The obtained results show the higher performance of the proposed GA compared with PSO in terms of solutions quality within comparatively shorter periods of time.

Keywords

Main Subjects

References

1- Dantzig, G. B. and Ramser, J. H. (1959). “ The truck dispatching problem.” Management Science, Vol. 6, No.1 , 80-91.
2- Bohoris, G.A. and Thomas, J. A. (1998). “A heuristic for vehicle routing and manpower Planning. ” Industrial Applications of Combinatorial Optimization, Vol.16, No.1, 256–271.
3- Lim, A., Rodrigues, B. and Song, L. (2004). “ Manpower allocation with time windows.” Journal of the Operational Research Society, Vol. 55, No. 11, 1178–1186.
4- Li, Y., Lim, A. and Rodrigues, B. (2005). “Manpower Allocation with Time Windows and Job-Teaming Constraints. ” Naval Research Logistics, Vol.52, No.4, 598–610.
5- Dohn, A., Kolind, E. and Clausen, J. (2009). “The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach.” Computers & Operations Research, Vol.36, No.4,1145-1157.
6- Bredstrom, D. and Ronnqvist, M. (2008). “Combined vehicle routing and scheduling with temporal precedence and synchronization constraints.” European Journal of Operational Research, Vol.191, No.1, 212-221.
7- Kim, B.I., Koo, J. and Park, J. (2010). “The combined manpower-vehicle routing problem for multi-staged services. ” Expert Systems with Applications, Vol. 37, No.12, 8424–8431.
8- Laurent, B. and Hao, J. (2007). “Simultaneous vehicle and driver scheduling: A case study in a limousine rental company. ” Computers & Industrial Engineering, Vol.53, No.3, 542-558.
9- Zapfel, G. and Bogl, M. (2008). “Multi-period vehicle routing and crew scheduling with outsourcing options. ” International Journal of Production Economics, Vol. 113, No.2, 980-996.
10- Hollis,B., Forbes, M. and Douglas, B. (2006). “Vehicle routing and crew scheduling for metropolitan mail distribution at Australia post. ”European Journal of Operational Research, Vol.173, No.1, 133-150.
11- Drexl, M., Rieck, J., Sigl, T. and Berning, B. (2013). “Simultaneous vehicle and crew routing and scheduling for partial and full load long-distance road transport.” BuR - Business Research, Vol.6, No.2, 242-264.
12- Rasmussen, M.S., Justesen, T., Dohn, A. and Larsen, J. (2012). “The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies.”European Journal of Operational Research, Vol.. 219, No.3, 273–289.
13- Thomsen, K. (2006).Optimization on home care, Informatics and Mathematical Modelling.
14- Bertels, S. Fahle, T. (2006). “A hybrid setup for a hybrid scenario: Combining Heuristics for the home health care problem.” Computers & Operations Research, Vol.33, No.10, 2866–2890.
15-Dohn, A., Rasmussen, M.S. and Larsen, J. (2011). “The vehicle routing problem with time windows and temporal dependencies.” Networks. Vol.58,  No. 4, 273–289.
16- Holland, J.H.(1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, MIT Press, Cambridge. (2ndedition in 1992).
17- Gen, M. and Cheng, R. (1997). “Genetic Algorithms & engineering design.” A Wiley Inter Science Publication.
18- Taguchi, G. (1986).“Introduction to quality engineering.” White Plains: Asian Productivity Organization.
19- Solomon, M.M. (1987). “Algorithms for the vehicle routing and scheduling problem with time window constraints.”  Operation Research, Vol. 35, No.2, 254-265.
Advances in Industrial Engineering
Volume 49, Issue 2 - Serial Number 2
پاییز و زمستان
October 2015
Pages 257-271

Files

Share

How to cite

Statistics