|
Graduation Thesis from 2014
Kim, Ji-Su
Ph.D. |
Refuse Collection Network Design and Vehicle Routing In Reverse Logistics This dissertation focuses on the refuse collection network design and vehicle routing problems in reverse logistics. The network design problem determines the number, locations and capacities of collection points as well as the allocations of refuses at each demand points to the opened collection points under the capacity and maximum allowable distance constraints, while the vehicle routing problem determines the number and routes of collection vehicles starting and terminating at the depot while satisfying the returned demands at collection points and vehicle capacity. In this dissertation, we first consider the two static and two dynamic network design models. Then, the integrated network design, capacity planning and vehicle routing problem is considered, together with reporting a case study on a Korean municipal refuse collection system.
In Chapter 2, two static collection network design models are suggested. The first one is the static problem that determines the locations of collection points and allocation of refuses at demand points to the opened collection points under the capacity and the maximum allowable distance constraints at each collection point. After formulating the problem mathematically, an optimal and two heuristic algorithms are suggested for the objective of minimizing the sum of fixed costs to open collection points and variable costs to transport refuses at demand points to collection points. The second one is the static collection network design and capacity planning problem. The capacity planning determines the capacities of collection points. Here, the additional capacity planning problem is an important consideration in collection network design since it provides flexible responses to changes in collection demands and cost savings from reducing
surplus collection capacities. To represent the problems mathematically, we develop an integer programming model. Then, due to the problem complexities, two heuristic algorithms are suggested. To show the performances of the algorithms developed for each
of the two static problems, computational experiments were done on various instances, and the test results are reported.
In Chapter 3, two dynamic collection network design models are suggested to cope with fluctuating demands commonly occurred in refuse collection systems. The first one is a restricted dynamic collection network design problem in which the locations are fixed, but the allocations are changed over a given planning horizon. This is because it is highly unlikely to change collection points due to large fixed costs to open or close them and larger total costs due to frequent changes in the locations of collection points. The
problem is formulated as an integer programming model for the objective of minimizing the sum of fixed costs and variable costs, and then, due to the problem complexity, two heuristic algorithms are suggested. As in the static models, the second one is the restricted dynamic network design and capacity planning problem. To represent the problem mathematically, an integer programming model is developed. Then, due to the problem complexity, two heuristics are suggested. To show the performances of the algorithms developed for each of the two dynamic problems, computational experiments were done on various test instances, and the results are reported. In particular, we show from an additional test that the dynamic approach significantly outperforms the static one when the refuse demands change over time.
In Chapter 4, an integrated model is suggested for network design, capacity planning and vehicle routing. The network design and capacity planning problems are to determine the static locations and capacities of collection points as well as the dynamic allocations of demand points to the opened collection points over a planning horizon, and the vehicle
routing problem is to determine the number and routes of vehicles in such a way that each collection point must be visited exactly once by one vehicle starting and terminating at the depot while satisfying the refuse demands at collection points and the vehicle capacity. The objective is to minimize the sum of fixed costs to open collection points and to acquire vehicles as well as variable costs to transport refuses at demand points to the opened collection points and travel the opened collection points by vehicles. To solve the integrated problem, two types of tabu search algorithms, hierarchical and integrated ones, are suggested. To show the performances of the tabu search algorithms, computational experiments were done on various test instances, and the results are reported. In particular, we show that the integrated approach outperforms the hierarchical one significantly. Also, a case study is reported for a Korean municipal refuse collection system. |
Daniel Cuche
M.S. |
A Multi-agent Evolutionary Algorithm for Job Shop Scheduling with Operators This thesis considers the job shop scheduling problem in which processing of an operation on a given machine has to be assisted by one of a limited number of operators, called job shop scheduling with operators. In this problem, besides determining the sequence of the jobs assigned to each machine, it is also needed to assign the jobs to operators and determine the sequence of the jobs assigned to each operator. After representing the problem using an extended disjunctive graph and an integer programming model for the objective of minimizing makespan, we suggest a multi-agent
evolutionary algorithm that incorporates a new neighborhood generation method. To test the performance of the algorithm suggested in this study, computational experiments
were done on benchmark instances, and the results show that the algorithm gives better solutions than the current best ones for the test instances in which the number of operators is up to around a half of the average of the number of jobs and machines. In particular, the proposed algorithm gave the optimal solutions for some test instances. |
Cho, Young Hye
M.S. |
Capacitated Dynamic Lot-sizing for Remanufacturing Systems: Mathematical Model and Solution Algorithm This thesis considers a dynamic lot-sizing problem in remanufacturing systems. Remanufacturing, one of product recovery options, is an emerging industry in which end-of-life products are reprocessed in such a way that their appearances and qualities are as good as new. In this study, we consider the system configuration with a single disassembly, parallel reprocessing and a single reassembly facilities, and the problem is to determine the disassembly, reprocessing and reassembly lot-sizes while satisfying the demands of remanufactured product over a given planning horizon. As an extension of
the previous study, we consider the capacity constraints explicitly, and hence more realistic solutions can be provided for operating remanufacturing systems. To represent the problem mathematically, a mixed integer programming model is developed for the
objective of minimizing the sum of setup, operation and inventory holding costs. Then, due to the complexity of the problem, we suggest fix-and-optimize heuristics in which the
solutions are obtained by fixing a portion of binary variables and solving the resulting mixed integer programming models iteratively. Computational experiments were done on various test instances and the results show that the heuristics give near optimal solutions. |
|
