- 學位論文
The Construction of a Prototype Software Solution for Vehicle Routing Problem Using Minimum Spanning Tree and TSP Approach
The Construction of a Prototype Software Solution for Vehicle Routing Problem Using Minimum Spanning Tree and TSP Approach
摘要
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.
並列摘要
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.