Pickup and delivery vehicle routing problem with time windows and precedence constraints | |
| Author | Nguyen Nguyen Tuan |
| Call Number | AIT Thesis no.ISE-03-19 |
| Subject(s) | SUBJECT 650 0 Vehicles Mathematical models Heuristic programming |
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of Engineering, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. ISE-03-19 |
| Abstract | This study addresses the Vehicle Routing Problem with Pick-Up and Delivery involving time windows and precedence constraints. Goods picked up from M markets are delivered to N customer locations by a fleet of homogeneous vehicles. The objective of the problem is to find routings to service all customers while minimizing the cost of travel and vehicles usage. The capacity and route time constraints of each vehicle should not be violated. The time window is soft, meaning that including waiting time and penalty for late time. Precedence constraints represent that the customers have their own and only one market. In this study, a tabu search based heuristic is proposed for obtaining an approximate solution to this problem. Firstly, the problem is solved following the insertion heuristic. And secondly, 2-opt, 2-opt*, Or-opt and Inter-tour are applied for route improvement. The heuristic performance was found to be efficient through a number of tests. Tahu search heuristic is tested with some modified benchmark problems. Time windows and precedence and other constraints were solved successfully. Some elements of tabu search are also studied in order to improve the quality of search process. |
| Year | 2003 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. ISE-03-19 |
| Type | Thesis |
| School | School of Advanced Technologies (SAT) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Anulark Techanitisawad; |
| Examination Committee(s) | Voratas Kachitvichyanukul;Huynh Trung Luong; |
| Scholarship Donor(s) | Ministry of Education and Training, Vietnam; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 2003 |