An algorithms for solving vehicle routing problems with probabilistic demands and multiple vehicles | |
| Author | Tran Minh Tri |
| Call Number | AIT Thesis no. ISE-01-26 |
| Subject(s) | Traveling-salesman problem Algorithms |
| Note | A thesis submitted in partial fulfilment of the requirements for the degree of Master of Engineering, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. ISE-01-26 |
| Abstract | In this thesis, a new variation of vehicle routing problem is developed. That is the vehicle routing problem with probabilistic demands and multiple vehicles. To solve it, a new algorithm is constructed. The problem can be briefly described as follows: a group of customers needs a certain kind of commodity, which is delivered by a fleet of vehicles. However, the demands of all customers are unknown until the first visit of a vehicle. The demands follow nonnegative discrete probability distributions. The objective is to determine the shortest routes for vehicles whereas all demands must be satisfied. The algoritlun is based on the state changing between stages in Markov chain. From one stage to another, one customer is served its full demand. Attaching to this process, a forward function of distance cost is calculated. At the end of the process, the minimum value of this cost function is determined and the optimal solution for vehicle's fleet is chosen. The algoritlun is an exact one. That means the algorithm yields the global optimality at the end of progress. Depending on the strength of coding language and computer's structure, the size of the problem can change. In the case of coding by Turbo C on PC Pentium III, the algorithm can solve from seven to ten customers. |
| Year | 2001 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. ISE-01-26 |
| 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 ;Tripathy, Arabinda; |
| Scholarship Donor(s) | Petro Vietnam ; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 2001 |