| Summary |
Chih-Hao Lai, 2006.07
Feng Chia University - Graduate Institute of Traffic and Transportation Engineering and Management
Recently, as the virtual approach is developing, such as electric business and TV shopping, etc. The form of product transfer is changing from traditional way into Home delivery. The traditional transportation transfers a large number of products to specific selling places or retailers, etc. And Home delivery is transfer a small number of products to customer. It is getting important to Home Delivery of domestic market, and it makes traditional transportation industry transfer to keep up with the market changes.
The study discusses the Vehicle Routing Problem (VRP) of home delivery car and Consider the constraint of Time Window to offer a Home Delivery assignment model. The design of planning is using known information to solve static VRP and improve initial solution by Tabu Search algorithm to obtain optimal delivery path. After operating car start delivery, we focus dynamic or canceling demands to start real time planning. We plan the shortest path Under Time window to save the routing cost and operate efficiently.
The practical Home Delivery is planning by sales driver whose duty area, so the study only consider one depot and one duty area to plan the delivery path. The method of research in time constraint is soft time windows and separate in morning and afternoon two times to fit in practical operation. In route planning, we design three stage planning. First two stages plan static demands and the third stage plans dynamic demands. Stage 1: Using the Nearest Neighborhood Heuristics to construct initial solution. Stage 2: Using Tabu Search algorithm to improve initial solution. The local search engine we use swap and op-opt interchange methods to make four alternatives and test in experimental design. After test, we choose the optimal alternative which is two times improving method to improve initial solution. Stage 3: As the real time demands occur, we start dynamic route planning improving.
After experimental design test, we find out in this way it can be almost reached 40% cost down improving effect. We put the optimal model into actual network to analyze and it also can be reached 20% cost down improving effect. |
