東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Algorithms and solutions to multi-le...

Chao, I-Ming.

Linked to FindBook

Google Book

Amazon

博客來

Algorithms and solutions to multi-level vehicle routing problems.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Algorithms and solutions to multi-level vehicle routing problems./
Author:	Chao, I-Ming.
Description:	1217 p.
Notes:	Source: Dissertation Abstracts International, Volume: 54-10, Section: B, page: 5366.
Contained By:	Dissertation Abstracts International54-10B.
Subject:	Operations Research. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9407615

Algorithms and solutions to multi-level vehicle routing problems.
Chao, I-Ming.

Algorithms and solutions to multi-level vehicle routing problems. - 1217 p.

Source: Dissertation Abstracts International, Volume: 54-10, Section: B, page: 5366.

Thesis (Ph.D.)--University of Maryland College Park, 1993.

In the famous classical Vehicle Routing Problem (VRP), a fleet of vehicles services a set of customers from a distribution depot to deliver or collect products. Each vehicle has a fixed capacity which cannot be exceeded and each customer has a known demand that must be fully satisfied. The objective is to provide each vehicle with a sequence of deliveries so that all customers are serviced and the total distance traveled by the fleet (or the total travel cost incurred by the fleet) is minimized without violating some other specified constraints. The Multi-level Vehicle Routing Problems (MLVRP) addressed in this dissertation contain at least two levels of decision making optimization in which the VRP is a specific level or a variant. However, the lowest level of the MLVRP is always a Traveling Salesman Problem (TSP) or a TSP-variant. The TSP is an NP-hard optimization problem, so the MLVRP's are at least as difficult as the TSP. For a large scale MLVRP, an exact method will be hard to get an optimal solution to the problem in a limited real world computation time. In the real world application, a heuristic method that can get a near optimal solution to the problem by using a reasonable computation time is preferred and practical. In this dissertation, five prototypes of the MLVRP are addressed. They are the orienteering problem, the team orienteering problem, the multi-depot vehicle routing problem, the period vehicle routing, and the period traveling salesman problem. For each type of problem, an effective heuristic method based upon a same simple basic idea is developed. The basic idea is that the algorithms accept some worse solutions when the searching procedure continues. When we make a decision of transitting a solution to another one, a set of candidates are considered one after one. Whenever a candidate can improve the objective function value, it is performed right away and all others are ignored. When no candidate can improve the objective function value, then one that losses the objective function value at the least will be performed if the amount of lossing value is not too many. The heuristics are implemented on the bench mark test problems taken from the literatures and the results are compared to those published along with the existing methods. A varieties of new test problems are also generated for each type of addressed MLVRP and are solved by the newly developed heuristics and by a new code of an existing methods or a carefully inspection. The comparisons for both sets of test problems for all five types of MLVRP show the superiority of the new heuristics. Finally, we synthesize the heuristics developed in this dissertation as a new general heuristic method for solving the MLVRP related optimization problems.Subjects--Topical Terms:

626629
Operations Research.

Algorithms and solutions to multi-level vehicle routing problems.
LDR:03637nmm 2200265 4500 001 1860984
005 20041111103532.5
008 130614s1993 eng d
035 $a (UnM)AAI9407615
035 $a AAI9407615
040 $a UnM $c UnM
100 1 $a Chao, I-Ming. $3 1948608
245 1 0 $a Algorithms and solutions to multi-level vehicle routing problems.
300 $a 1217 p.
500 $a Source: Dissertation Abstracts International, Volume: 54-10, Section: B, page: 5366.
500 $a Chairman: Bruce L. Golden.
502 $a Thesis (Ph.D.)--University of Maryland College Park, 1993.
520 $a In the famous classical Vehicle Routing Problem (VRP), a fleet of vehicles services a set of customers from a distribution depot to deliver or collect products. Each vehicle has a fixed capacity which cannot be exceeded and each customer has a known demand that must be fully satisfied. The objective is to provide each vehicle with a sequence of deliveries so that all customers are serviced and the total distance traveled by the fleet (or the total travel cost incurred by the fleet) is minimized without violating some other specified constraints. The Multi-level Vehicle Routing Problems (MLVRP) addressed in this dissertation contain at least two levels of decision making optimization in which the VRP is a specific level or a variant. However, the lowest level of the MLVRP is always a Traveling Salesman Problem (TSP) or a TSP-variant. The TSP is an NP-hard optimization problem, so the MLVRP's are at least as difficult as the TSP. For a large scale MLVRP, an exact method will be hard to get an optimal solution to the problem in a limited real world computation time. In the real world application, a heuristic method that can get a near optimal solution to the problem by using a reasonable computation time is preferred and practical. In this dissertation, five prototypes of the MLVRP are addressed. They are the orienteering problem, the team orienteering problem, the multi-depot vehicle routing problem, the period vehicle routing, and the period traveling salesman problem. For each type of problem, an effective heuristic method based upon a same simple basic idea is developed. The basic idea is that the algorithms accept some worse solutions when the searching procedure continues. When we make a decision of transitting a solution to another one, a set of candidates are considered one after one. Whenever a candidate can improve the objective function value, it is performed right away and all others are ignored. When no candidate can improve the objective function value, then one that losses the objective function value at the least will be performed if the amount of lossing value is not too many. The heuristics are implemented on the bench mark test problems taken from the literatures and the results are compared to those published along with the existing methods. A varieties of new test problems are also generated for each type of addressed MLVRP and are solved by the newly developed heuristics and by a new code of an existing methods or a carefully inspection. The comparisons for both sets of test problems for all five types of MLVRP show the superiority of the new heuristics. Finally, we synthesize the heuristics developed in this dissertation as a new general heuristic method for solving the MLVRP related optimization problems.
590 $a School code: 0117.
650 4 $a Operations Research. $3 626629
650 4 $a Applied Mechanics. $3 1018410
690 $a 0796
690 $a 0346
710 2 0 $a University of Maryland College Park. $3 1249734
773 0 $t Dissertation Abstracts International $g 54-10B.
790 1 0 $a Golden, Bruce L., $e advisor
790 $a 0117
791 $a Ph.D.
792 $a 1993
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9407615