|
Graduation Thesis from 2007
Cho, Byeong Min
M.S. |
Two-Stage Heuristic for Period Vehicle Routing: Minimizing the Fleet Size This thesis focuses on period vehicle routing, a multi-period extension of the classical capacitated vehicle routing problem, for the objective of minimizing the maximum number of vehicles simultaneously required over the planning horizon, i.e., the fleet size. In the problem, each customer can be visited one or more times over the planning horizon according to the service combinations of that customer, and the vehicle capacity and the travel time constraints must be satisfied. Due to the complexity of the problem, we suggest a two-stage heuristic algorithm. In the first stage, an initial solution is obtained by assigning a service combination to each customer, updating the routes by inserting each customer to the routes formed so far, and allocating the routes to vehicles while considering the available travel time. Then, the initial solution is improved by changing the service combination assigned to each customer. To show the performance of the two-stage heuristic, computational experiments are done on a number of randomly generated test problems, and the results show that the algorithm suggested in this thesis outperforms the exist ing one. |
Kwon, Yong Ju
M.S. |
A Tabu Search Algorithm using Voronoi Diagram for the Capacitated Vehicle Routing Problem This thesis considers the vehicle routing problem, which is the problem of determining the vehicle routes for the objective of minimizing total traveling costs. This problem is an extension of the traveling salesman problem. Each customer can be visited exactly once by exactly one vehicle . Also, the vehicle capacity and the travel time constrains must be satisfied. Due to the complexity of the problem, this thesis suggests tabu search algorithm using the proximity information by the voronoi diagram. To show the performance of the heuristic algorithm computational experiments are done on the benchmark problems and the results are reported. |
Kim, Jae Dong
M.S. |
Vehicle Routing in a Refuse collection system: A Case study This thesis addresses a case study on the vehicle routing problem for a refuse collection activity in Seoul, South Korea. Unlike the existing deterministic version of the vehicle routing problem, this thesis considers a stochastic version of the vehicle routing problem that determines the collection vehicle routes that satisfy the stochastic demand at each collection point for the objective of minimizing the total distance travelled. Due to the stochasticity of demand at each collection point, the vehicle capacity may be violated at random, called a route failure in this thesis. Two types of simple heuristics, deterministic and stochastic ones, are suggested. To show the performances of the heuristics, simulation experiments were done on the real data, and the results show that deterministic and stochastic heuristics suggested in this thesis outperforms the conventional method used in the current refuse collection activity. |
Kim, Ji Su
M.S. |
Heuristic Algorithms for the Capacitated Collection Network Design Problem Refuse collection, one of important compositions in reverse logistics, is an activity rendering recyclables or wastes and moving them to some points where further treatment is taken care of. Among various decisions in the activity, we focus on the network design, which is the problem of locating the collection points as well as allocating the refuse demands to the collection points while satisfying the capacity contraint at each collection point for the objective of minimizing the sum of fixed and transportation costs. Here, the collection point is the place where recyclables or wastes near the point are gathered, and locating the collection points is done by selecting them from a given set of potential sites. An integer programming model is suggested to represent the problem and several heuristic algorithms are suggested due to the complexity of the problem. Computational experiments were done on randomly generated test problem up to 500 potential sites, and the results are reported. In particular, some of the heuristics gave the near optimal solutions for small-size problems, i.e.,those within 2% gaps from the optimal solution values. |
|
