Using population-based incremental learning to optimize feasible distribution logistic solutions

[摘要] 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. Themapping of the customers in the problem and the vehicle routes on a time grid enables theutilization of the powerful genetic search that the PBIL algorithm provides in liaison withcompetitive learning. The problem consists of a number of customers who may at any timeof the day place an order on another customer for some package. The fleet of vehiclestravelling between the customers must then combine powers to pickup and deliver thepackage as fast as possible without ever leaving their assigned routes. The solution to thisproblem then, is a set of routes for the fleet that will minimize some percentile of thedelivery times between customers. The PBIL meta-heuristic provides the blueprint of thefinal algorithm, where the final algorithm is actually just a normal PBIL algorithm withsome external solution generation and evaluation techniques employed. The final algorithmcan easily solve an instance of the problem in polynomial time, given that the resolution ofthe time grid used is not too small.

[发布机构] Stellenbosch University