Title

The Construction of a Prototype Software Solution for Vehicle Routing Problem Using Minimum Spanning Tree and TSP Approach

Translated Titles

The Construction of a Prototype Software Solution for Vehicle Routing Problem Using Minimum Spanning Tree and TSP Approach

Authors

Rahi

Key Words

Vehicle routing problem ; Capacitated VRP ; Heuristic methods ; Software prototyping ; Vehicle routing problem ; Capacitated VRP ; Heuristic methods ; Software prototyping

PublicationName

臺北科技大學管理國際學生碩士專班 (IMBA)學位論文

Volume or Term/Year and Month of Publication

2014年

Academic Degree Category

碩士

Advisor

Yu-Hsien Lin

Content Language

英文

Chinese Abstract

Vehicle routing problem (VRP) was first introduced by Dantizng & Ramser in 1959. The objective is to visit and serve a number of customers with a fleet of vehicles. Since it was introduced, many studies have been conducted by researchers to solve this NP-hard combinational problem. Today, due to the importance of VRP as a well-known and critical problem in logistics networks, many variants of the problem has been modeled and several software solution packages are offered to fulfill the need for VRP in industry. In this thesis, we first propose a heuristic algorithm for single depot non-directional VRP with time limitations, using clustered TSP approach, which is a two-phase constructive approach that clusters the customers in identical groups first and then solves those individual TSPs using MST and paring method. Furthermore, based on our algorithm, we propose a prototype of an interactive software solution which is applicable to small and medium-sized VRP instances where full customized solution is demanded by route designers.

English Abstract

Vehicle routing problem (VRP) was first introduced by Dantizng & Ramser in 1959. The objective is to visit and serve a number of customers with a fleet of vehicles. Since it was introduced, many studies have been conducted by researchers to solve this NP-hard combinational problem. Today, due to the importance of VRP as a well-known and critical problem in logistics networks, many variants of the problem has been modeled and several software solution packages are offered to fulfill the need for VRP in industry. In this thesis, we first propose a heuristic algorithm for single depot non-directional VRP with time limitations, using clustered TSP approach, which is a two-phase constructive approach that clusters the customers in identical groups first and then solves those individual TSPs using MST and paring method. Furthermore, based on our algorithm, we propose a prototype of an interactive software solution which is applicable to small and medium-sized VRP instances where full customized solution is demanded by route designers.

Topic Category 管理學院 > 管理國際學生碩士專班 (IMBA)
社會科學 > 管理學
Reference
  1. [4] Christos H. Papadimitriou and Kenneth Steiglitz (1998), “Combinatorial Optimization: Algorithms and Complexity (1th ed.)’, Dover Publications
    連結:
  2. [5] Geir Hasle and Oddvar Kloster (2007), “Industrial Vehicle Routing”, Information and Communication Technology (ICT) / Publications
    連結:
  3. [6] T.K. Ralphsy, L. Kopmanz, W.R. Pulleyblankx, and L.E. Trotter, Jr. (2001), “On the Capacitated Vehicle Routing Problem”, SIAM Journal of Discrete Mathematics
    連結:
  4. [7] G.laporte. (1991), “Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms”, European Journal of Operational Research, p.513-20
    連結:
  5. [1] COM (2006) 336 “Freight Transport Logistics in Europe – the key to sustainable mobility”, Commission of The European Communities, p.2-5
  6. [2] Paolo Toth and Daniele Vigo (2002), “The Vehicle Routing Problem”, Society for Industrial and Applied Mathematics, Ch. 1-5
  7. [3] F.Rothlauf (2011) “Design of Modern Heuristics (1th ed.)”, Berlin, Heidelberg, Germany, p.45-40
  8. [8] G.Laporte and F.Semet (2002), “A Guide to Vehicle Routing Heuristics”, Operational Research Society
  9. [9] OR/MS Today Magazine (February 2012), “Vehicle Routing Software Survey”, The INFORMS Society, p.1-17
  10. (Accessible online on the link: http://www.orms-today.org/surveys/Vehicle_Routing/vrss.html)