The Vehicle Routing Problem: Latest Advances and New Challenges
The Vehicle Routing Problem (VRP) has been an especially active and fertile area of research. Over the past five to seven years, there have been numerous technological advances and exciting challenges that are of considerable interest to students, teacher
- PDF / 347,916 Bytes
- 12 Pages / 441 x 666 pts Page_size
- 26 Downloads / 199 Views
Department of Mathematics University of Maryland College Park, MD 20742 [email protected]
2
Robert H. Smith School of Business Department of Decision and Information Technologies University of Maryland College Park, MD 20742 [email protected]
3
Kogod School of Business American University Washington, DC 20016 [email protected]
Summary. In this chapter, we use genetic algorithms (GAs) to solve the generalized orienteering problem (GOP). In the orienteering problem (OP), we are given a transportation network in which a start point and an end point are specified, and other points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of the other locations in order to maximize the total path score. In the GOP, each point has a score with respect to a number of attributes (e.g., natural beauty, historical significance, cultural and educational attractions, and business opportunities) and the overall objective function is nonlinear. The GOP is more difficult than the OP, which is itself NP-hard. An effective heuristic using artificial neural networks (ANNs), however, has been designed to solve the GOP. In this chapter, we show that a straightforward GA can yield comparable results. Key words: Generalized orienteering problem; genetic algorithm.
1 Introduction The orienteering problem has been studied extensively in the literature since the early 1980s. In the orienteering problem (OP), we are given a transportation network in which a start point and an end point are specified, and other B. Golden et al. (eds.), The Vehicle Routing Problem, c Springer Science+Business Media, LLC 2008 doi: 10.1007/978-0-387-77778-8 12,
264
Wang, Golden, and Wasil
points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of the other locations in order to maximize the score of the total path. In the GOP, each point has a score with respect to a number of attributes and the overall objective function is nonlinear. The GOP is more difficult than the OP, which is itself NP-hard [6]. Therefore, researchers have proposed a variety of heuristics for these two problems. Wang et al. [6, 7] applied artificial neural networks to obtain high-quality solutions to the OP and GOP in a reasonable amount of time. Chao et al. [1] applied deterministic annealing to the OP and also obtained high-quality results. Gendreau et al. [3] applied tabu search to the OP and obtained near-optimal solutions to instances with up to 300 nodes. Laporte and Rodr´ıquez-Mart´ın [4] present a recent overview. Now consider the following hypothetical problem. A traveler comes to China and has time to visit several cities. The traveler has multiple goals in mind (e.g., enjoy the natural beauty of the country, visit sites of historical interest, attend some major cultural events, and identify promising business opportunities). Since travel between Chinese cities is expensive and our traveler must adhere to a budget restriction, we imp
Data Loading...
