Using population-based incremental learning to optimize feasible distribution logistic solutions
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.