Journal of Korean Society of Transportation (대한교통학회지)

Korean Society of Transportation (대한교통학회)
권호 표지

Multiobjective Routing and Scheduling for Vehicles Transporting Hazardous Materials

위험물 운송차량의 다목적 경로 및 스케줄 관리 방안

  • Published : 2007.10.30
Download PDF
⟨ Previous Next ⟩

Abstract

Vehicles transporting hazardous materials can make huge damage to people, properties and environment by traffic accidents. Therefore, transporting hazardous materials is a big issue with the cutting edge technology of communications in these days. However, despite this situation, Korean government gives limited efforts for systematic management, research and investment about hazardous materials. Accordingly, this research suggests the key path finding algorithm about management of real-time schedule and routes for vehicles transporting hazardous materials. Besides, the case study is progressed in transportation networks of Seoul in order to evaluate the reality of algorithm. Specifically, time-space network transformation is performed for time window attributes. In addition, this study proposes the techniques searching for non-dominated paths considering schedule by the multiobjective shortest path algorithm based on dynamic programming in dynamic transportation networks including multiobjective attributes.

위험물 운송차량은 사고발생 시 위험물의 종류에 따라 일반차량의 사고와는 비교도 안 될 정도의 인명, 재산, 환경피해를 유발한다. 또한 산업화와 도시화의 심화에 따른 위험물의 양과 종류의 증가는 시민의 안전을 위해 위험물의 안전한 운송과 처리 문제를 매우 민감한 사항으로 대두시켰다. 하지만 국내에서는 최첨단 통신장비가 실용화되고 있음에도 불구하고, 선진국과는 달리 위험물 운송차량의 체계적인 관리와 연구 및 투자가 아직까지는 초보적인 단계에 머물러 있는 것이 현실이다. 이에 본 연구에서는 실시간으로 운행될 위험물 운송차량의 스케줄과 경로를 관리하는 방안을 제시하기 위한 핵심이 되는 경로탐색기법을 제안하고자 한다. 동시에 서울시와 같은 도시를 대상으로 현실적인 적용의 가능성을 평가하고자 한다. 구체적으로는 시간창 속성을 고려하기 위해 시간-공간 네트워크 변형을 하였으며, 다목적 속성이 존재하는 동적 교통망에 대하여 동적 계획법에 근거한 다목적 최적경로탐색 알고리즘의 수행을 통해 스케줄을 고려하는 비지배경로를 탐색하는 기법을 제안하고자 한다.

Keywords

References

  1. 김시곤.안승범(1999.6), 'GIS를 활용한 위험물 수송 관리시스템개발 (울산시 사례연구)', 대한교통학회지, 제17권 제2호, 대한교통학회, pp.29-40
  2. 신성일(2004), '교통망에 적합한 K 비루프 경로 탐색 알고리즘', 대한교통학회지, 제22권 제6호, 대한교통학회, pp.121-131
  3. 조용성.오세창(1999.3), '위험물 수송을 위한 위험도 및 최적경로산정 -수도권 사례를 중심으로', 대한교통학회지, 제17권 제1호, 대한교통학회, pp.75-89
  4. 조종석(2006), '환승과 운행시간 스케줄을 고려한 통합교통망에서의 동적K경로탐색알고리즘, 박사 학위논문, 서울대학교
  5. Azevedo, J. A., Costa, M. E. O. S., Madeira J.J.E.R.S., and Martins E.Q.V (1993), 'An Algorithm for the Ranking of Shortest Paths', European Journal of Operational Research, Vol.69, pp.97-106 https://doi.org/10.1016/0377-2217(93)90095-5
  6. Brumbaugh-Smith, J., and Shoer, D. (1989), 'An Empirical Investigation of Some Bicriterion- Shortest Path Algorithms', European Journal of Operational Research, 43, pp.216-224
  7. Cox, R. G. (1984), 'Routing and Scheduling of Hazardous Materials Shipments: Algorithmic Approaches to Managing Spent Nuclear Fuel Transport', Ph.D. Dissertation, Cornell Univ., Ithaca, N.Y
  8. Climaco, J.C.M. and Martins, E.Q.V. (1982), 'A Bicriterion Shortest Path Algorithm', European Journal of Operational Research, 11, p.p399-404 https://doi.org/10.1016/0377-2217(82)90205-3
  9. Desaulniers, G., and Villeneuve, D. (2000), 'The Shortest Path Problem with Time Windows and Linear Waiting Costs', Transp. Sci., 34, pp.312-319 https://doi.org/10.1287/trsc.34.3.312.12298
  10. Erkut, E., and Verter, V.(1995), 'Hazardous Materials Logistics. Facility Location: A Survery of Application and Methods', Z. Drezner, ed., Springer, New York, pp.466-506
  11. Hansen, P., (1980), 'Bicriterion Path Problems. In: Fandel, G., Gal, T. (Eds.), Multiple Criteria Decision Making: Theory and Applications, Lectures Notes in Economics and in Mathematical Systems', Vol. 177, Springer, Heidelberg, pp.109-127
  12. Iakovou, E. T., Douligeris, C., Ip, C., Liu, H., and Yudhibir. L.(1999), 'A Maritime Global Route Planning Model for Hazardous Materials Transportation', Transp. Sci., 33, pp.34-48 https://doi.org/10.1287/trsc.33.1.34
  13. List. G. F., Mirchandani, P. B., Turnquist, M.A.. and Zografos. K. G. (1991), 'Modeling and Analysis for Hazardous Materials Transportation: Risk Analysis, Routing/ Scheduling and Facility Location', Transp. Sci., 25, pp.100-114 https://doi.org/10.1287/trsc.25.2.100
  14. Martins, E.Q.V. (1984), 'On A Multicriteria Shortest Path Problem', European Journal of Operational Research, 16, pp.236-245 https://doi.org/10.1016/0377-2217(84)90077-8
  15. Mote, J., Murthy, I., and Olson D.L. (1991), 'A Parametric Approach to Solving Bicriterion Shortest Path Problems', European Journal of Operational Research, 53, pp.81-92 https://doi.org/10.1016/0377-2217(91)90094-C
  16. Nozick, L. K., List, G. G., and Turnquist. M. A. (1997), 'Integrated Routing and Scheduling in Hazardous Materials Transportation', Transp. Sci., 31, pp.200-215 https://doi.org/10.1287/trsc.31.3.200
  17. Paolo Serafini (2005), 'Dynamic Programming and Minimum Risk Paths', European Journal of Operational Research, pp.224-237
  18. Pasquale Carotenuto.Stefano Giordani. Salvatore Ricciardelli (2005), 'Finding Minimum and Equitable Risk Routes for Hazmat Shipments', Computers & Operations Research, pp.1304-1327
  19. Qiang Meng . Der-Horng Lee . Ruey Long Cheu (2005), 'Multiobjective Vehicle Routing and Scheduling Problem with Time Window Constraints in Hazardous Material Transportation', Journal of Transportation Engineering, pp.699-707
  20. Skriver, A.J.V. and Andersen, K.A. (2000), 'A Label Correcting Approach for Solving Bicriterion Shortest-Path Problems', Computers & Operations Research, 27, pp.507-524 https://doi.org/10.1016/S0305-0548(99)00037-4
  21. Sulijoadikusumo, G. S., and Nozick, L. K. (1998), 'Multiobjective Routing and Scheduling of Hazardous Materials Shipments', Transportation Research Record 1613, Transportation Research Board, Washington, D.C., pp.96-104
  22. Turnquist. M. A. (1987), 'Routes, Schedules and Risks in Transporting Hazardous Materials. Strategic Planning in Energy and Natural Resources', B. Lev., J. A. Bloom, A. J. Gleit, F. H. Murphy and C. Shoemaker. eds., Elsevier Science, Amsterdam, pp.289-302
  23. Wijeratne. A. B., Turnquist. M. A., and Mirchandani. P. B. (1993), 'Multiobjective Routing of Hazardous Materials in Stochastic Networks', European Journal of Operational Research., 65, pp.33-43 https://doi.org/10.1016/0377-2217(93)90142-A
  24. Zografos K.G., Androutsopoulos K.N.(2004), 'A Heuristic Algorithm for Solving Hazadous Materials Distribution Problems', European Journal of Operational Research, 152(2), pp.507-519 https://doi.org/10.1016/S0377-2217(03)00041-9