IE interfaces (산업공학)

Korean Institute of Industrial Engineers (대한산업공학회)
권호 표지

Transporter Scheduling for Dynamic Block Transportation Environment

동적 블록수송환경을 위한 트랜스포터 일정계획

  • Lee, Woon-Seek (Systems Management and Engineering, Pukyong National University) ;
  • Lim, Won-Il (Systems Management and Engineering, Pukyong National University) ;
  • Koo, Pyung-Hoi (Systems Management and Engineering, Pukyong National University) ;
  • Joo, Cheol-Min (System and Management Engineering, Dongseo University)
  • 이운식 (부경대학교 시스템경영공학과) ;
  • 임원일 (부경대학교 시스템경영공학과) ;
  • 구평회 (부경대학교 시스템경영공학과) ;
  • 주철민 (동서대학교 시스템경영공학과)
  • Received : 2008.04.14
  • Accepted : 2008.06.09
  • Published : 2008.09.30
Download PDF
⟨ Previous Next ⟩

Abstract

This paper considers a transporter scheduling problem under dynamic block transportation environment in shipbuilding. In dynamic situations, there exist the addition or cancellation of block transportation requirements, sudden breakdowns and maintenance of transporters. The transportation of the blocks in the shipyard has some distinct characteristics. Some blocks are available to be picked up at a specific time during the planning horizon while some other blocks need to be delivered before a specific time. These requirements cause two penalty times : 1) delay times incurred when a block is picked up after a required start time, and 2) tardy times incurred when a block shipment is completed after the required delivery time. The blocks are located at different areas in the shipyard and transported by transporters. The objective of this paper is to propose heuristic algorithms which minimize the weighted sum of empty transporter travel times, delay times, and tardy times. Four heuristic algorithms for transporter scheduling are proposed and their performance is evaluated.

Keywords

References

  1. Baker, E. K. (1983), An Exact Algorithm for the Time-Constrained Traveling Salesman Problem, Opns. Res., 31, 939-945
  2. Bard, J. F., Kontoravdis, G., and Yu, G. (2002), A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows, Transportation Sci., 36, 250-269 https://doi.org/10.1287/trsc.36.2.250.565
  3. Bianco, L., Mingozzi, A., and Sicciardelli, S. (1998), Dynamic Programming Strategies for the Traveling Salesman Problem with Time Windows and Precedence Constraints, Opns. Res., 45, 365-378 https://doi.org/10.1287/opre.45.3.365
  4. Calvo, R. W. (2000), A New Heuristic for the Traveling Salesman Problem with Time Windows, Transportation Sci., 34, 113-124 https://doi.org/10.1287/trsc.34.1.113.12284
  5. Chao, I. M. (2002), A Tabu Search Method for Truck and Trailer Routing Problem, Computers and O.R., 29, 33-51 https://doi.org/10.1016/S0305-0548(00)00056-3
  6. Chung, K. H., Baek, T. H., Min, S. G., Kim, H. S., Park, J. C., Cho. K. K., and Park, C. K. (2001), Development of the Spatial Scheduling System and Its Applications in Shipbuilding Industry, IE Interfaces, 14(4), 394-402
  7. Crainic, T. G. and Laporte, G. (1998), Fleet Management and Logistics, Kluwer Academic Publishers
  8. Desrosiers, J., Sauve, M., and Soumis, F. (1988), Lagrangian Relaxation Methods for Solving the Minimum Fleet Size Multiple Traveling Salesman Problem with Time Windows, Management Sci., 34, 1005-1022 https://doi.org/10.1287/mnsc.34.8.1005
  9. Dumas, Y., Desrosiers, J., Gelinas, E., and Solomon, M. M. (1995), An Optimal Algorithm for the Traveling Salesman Problem with Time Windows, Opns. Res., 45, 367-371
  10. Gendreau, M., Hertz, A., Laporte, G., and Stan, M. (1998), A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows, Opns. Res., 46, 330-335 https://doi.org/10.1287/opre.46.3.330
  11. Ha, T. R., Moon, C. U., Joo, C. M., and Park, J. C. (2000), A Hybrid Genetic Algorithm for Scheduling of the Panel Block Assembly Shop in Shipbuilding, Management Science, 17(1), 135-143
  12. Joo, C. M., Lee, W. S., Koo, P. H., and Lee, K. B. (2006), Transporter Scheduling for Block Transportation in Shipbuilding, J. of the Korea Management Engineers Society, 11(3), 169-179
  13. Ko, C. S., Jung, K. H., and Shin, J. Y. (2000), Determination of Vehicle Fleet Size for Container Shuttle Service, Management Science, 17(2), 87-95
  14. Koh, S. G., Park, J. C., Choi, Y. S., and Joo, C. M. (1999), Development of a Block Assembly Scheduling System for Shipbuilding Company, IE Interfaces, 12(4), 586-594
  15. Koo, P. H., Lee, W. S., and Jang, D. W. (2004), Fleet Sizing and Vehicle Routing for Container Transportation in a Static Environment, OR Spectrum, 26, 193-209 https://doi.org/10.1007/s00291-003-0152-4
  16. Langevin, A., Desrochers, M., Kesrosiers, J., and Foumis, F. (1993), A Two Commodity Flow Formulation for the Traveling Salesman and Makespan Problems with Time Windows, Network, 23, 631-640 https://doi.org/10.1002/net.3230230706
  17. Laporte, G. and Osman, H. (1995), Routing Problems: a Bibliography, Annal of OR., 61, 227-262 https://doi.org/10.1007/BF02098290
  18. Maxwell, W. L. and Muckstadt, J. A. (1982), Design of Automated Guided Vehicle Systems, IIE Trans., 14, 114-124
  19. Park, M. H., Lee, W. S., Ock, Y. S., and Lee, T. E. (1995), A Review of Korean Shipbuilding Industry and Industrial Engineering Research, IE Interfaces, 8(2), 5-20
  20. Pesant, G., Gendreau, M., Potvin, J.-Y., and Rousseau, J.-M. (1998), An Exact Constraint Logic Programming Algorithm for the TSP with Time Windows, Transportation Sci., 32, 12-29 https://doi.org/10.1287/trsc.32.1.12
  21. Savelsbergh, M. W. P. (1985), Local Search in Routing Problems with Time Windows, Ann. Opns. Res., 4, 285-305 https://doi.org/10.1007/BF02022044