Thesis (MScEng (Industrial Engineering))--University of Stellenbosch, 2005. / This thesis introduces an adaptation of the Population-Based Incremental Learning (PBIL)
meta-heuristic implemented on a variant of the General Pickup and Delivery Problem. The
mapping of the customers in the problem and the vehicle routes on a time grid enables the
utilization of the powerful genetic search that the PBIL algorithm provides in liaison with
competitive learning. The problem consists of a number of customers who may at any time
of the day place an order on another customer for some package. The fleet of vehicles
travelling between the customers must then combine powers to pickup and deliver the
package as fast as possible without ever leaving their assigned routes. The solution to this
problem then, is a set of routes for the fleet that will minimize some percentile of the
delivery times between customers. The PBIL meta-heuristic provides the blueprint of the
final algorithm, where the final algorithm is actually just a normal PBIL algorithm with
some external solution generation and evaluation techniques employed. The final algorithm
can easily solve an instance of the problem in polynomial time, given that the resolution of
the time grid used is not too small.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/1601 |
| Date | 03 1900 |
| Creators | Lourens, Tobie |
| Contributors | Van Wijck, W., University of Stellenbosch. Faculty of Engineering. Dept. of Industrial Engineering. |
| Publisher | Stellenbosch : University of Stellenbosch |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Rights | University of Stellenbosch |
Page generated in 0.0026 seconds