ABSTRACT
In this paper, we propose a manpower allocation model with time windows which is of practical interest to serviceman scheduling operations. Specifically, this problem originates from peculiar port yard scheduling needs where demand is generated from locations in the yard for servicemen who are dispatched from a central point and where the objectives are to minimize the number of servicemen scheduled, travel distances, travel times and waiting times at each location. Although closely related to the well-known vehicle routing problem, this problem is different while its solution could provide insight to the latter. We develop solutions using metaheuristic methods, and in particular provide tabu-embedded simulated annealing and squeaky wheel optimization with local search algorithms for this problem. We apply these newly-developed metaheuristics with adaptations for solutions to the manpower allocation problem, while our analysis throws light on how these work. Computational results are reported which show the effectiveness of our approach when applied to the manpower allocation problem.
- Backer, B., Furnon, V. Shaw, P., Kilby, P. Prosser, P., (2000), Solving vehicle routing problem using constraint programming and metaheuristics, Journal of Heuristics 6, pp. 501--523. Google ScholarDigital Library
- Chiang, W., Russell, R., (1997), A reactive tabu search metaheuristics for the vehicle routing problem with time window, INFORMS Journal on Computing 9, pp. 417--430.Google ScholarDigital Library
- Cordeau, J., Laporte, G., Mercier, A., (2000), A unified tabu search heuristic for vehicle routing problem with time windows, Technical Report. CRT-00-03, Center for Research on Transportation, Montreal, Canada.Google Scholar
- Eilon, S., Watson-Gandy C. and Christofides, N., (1971), Distribution Management: Mathematical Modeling and practical Analysis. Hafner, New York.Google Scholar
- Homberger, J., Gehring, H., (1999), Two evolutionary metaheuristics for the vehicle routing problem with time window, INFOR 37 pp. 165--172.Google Scholar
- Joslin, D. and Clements, David P., (1998) "Squeaky Wheel" Optimization, AAAI/IAAI 1998, pp. 340--346. Google ScholarDigital Library
- Li, H. B. and Lim, A. (2002) Local Search with Annealing-like Restarts to solve the VRPTW, European Journal of Operational Research, accepted for publication. Google ScholarDigital Library
- Li, H. B. and Lim, A. (2001), A Metaheuristic for solving the pickup and delivery problem with time windows, The 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI-2001, Dallas, USA), 151--158. Google ScholarDigital Library
- Pardalos, P. and Resende, M., Editors, (2002), Handbook of Applied Optimization, Oxford University Press.Google Scholar
- Rochat, Y., Taillard, E., (1995), Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics 1 pp. 147--167.Google ScholarDigital Library
- Rousseau, J., Gendreau, M., Pesant, G. (2002) Using constraint-based operators to solve the vehicle routing problem with time windows, Journal of Heuristics 8(1), pp. 43--58. Google ScholarDigital Library
- Savelsbergh, M., (1985), Local search for routing problem with time windows, Annals of Operations Research 4, pp. 285--305.Google ScholarCross Ref
- Solomon, M., (1987) Algorithms for the vehicle routing and scheduling problems with time window constrains, Operations Research 35, pp. 254--264. Google ScholarDigital Library
- Thangiah, S. R., (1999), A hybrid genetic algorithm, simulated annealing and tabu search heuristics for the vehicle routing problem with time windows, In Chambers, Editor, Practical Handbook of Genetic Algorithms: Complex Coding Systems, Vol. III, CRC Press, Boca Raton, pp. 253--277.Google Scholar
- Taillard, E., Badeau, P. Gendreau, M. Geurtin, F., Potvin, J., (1997) A tabu search heuristic for the vehicle routing problem with time windows, Transportation Science 31 170--186.Google ScholarDigital Library
Recommendations
Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties
A novel idle time insertion algorithm.A new algorithm of implicit enumeration.A new efficient heuristic algorithm for solving the addressed problem. This paper addresses the single machine scheduling problem with distinct time windows and sequence-...
A GRASP for Parallel Machine Scheduling with Time Windows
This paper presents a greedy randomized adaptive search procedure (GRASP) for scheduling n jobs on m nonhomogeneous parallel machines with time windows. An additional feature of the problem is that each job falls into one of ρ priority classes. The ...
Crossdock truck scheduling with time windows: earliness, tardiness and storage policies
This article proposes to simultaneously plan inbound and outbound truck arrivals and departures in a cross-docking platform, as well as the internal pallet handling. The objective is to minimize both the total number of pallets put in storage and the ...
Comments