An initial solution heuristic for the vehicle routing and scheduling problem.

[摘要] South Africa provides a fascinating interface between the developed and the developing world and poses a multitude of opportunities for enhancing the sustainable development of local cities. The concept of City Logistics is concerned with the mobility of cities, and entails the process of optimizing urban logistics activities by considering the social, environmental, economic, financial, and energy impacts of urban freight movement. Vehicle routing and scheduling has the potential to address a number of these key focus areas. Applying optimization to vehicle routing and scheduling results in a reduced number of trips, better fleet utilization, and lower maintenance costs; thereby improving the financial situation of the fleet owner. Improved fleet utilization could have a positive environmental impact, while also improving the mobility of the city as a whole. Energy utilization is improved while customer satisfaction could also increase through on-time deliveries and reliability. The Vehicle Routing Problem (VRP) is a well-researched problem in Operations Research literature. The main objective of this type of problem is to minimize an objective function, typically distribution cost for individual carriers. The area of application is wide, and specific variants of the VRP transform the basic problem to conform to application specific requirements. It is the view of this dissertation that the various VRP variants have been researched in isolation, with little effort to integrate various problem variants into an instance that is more appropriate to the South African particularity with regards to logistics and vehicle routing. Finding a feasible, and integrated initial solution to a hard problem is the first step in addressing the scheduling issue. This dissertation attempts to integrate three specific variants: multiple time windows, a heterogeneous fleet, and double scheduling. As the problem is burdened with the added constraints, the computational effort required to find a solution increases. The dissertation therefore also contributes to reducing the computational burden by proposing a concept referred to as time window compatibility to intelligently evaluate the insertion of customers on positions within routes. The initial solution algorithm presented proved feasible for the integration of the variants, while the time window compatibility decreased the computational burden by 25%, and as much as 80% for specific customer configurations, when using benchmark data sets from literature. The dissertation also improved the quality of the initial solution, for example total distance traveled, by 13%. Finding an initial solution is the first step in solving vehicle routing problems. The second step is to improve the initial solution iteratively through an improvement heuristic in an attempt to find a global optimum. Although the improvement heuristic falls outside the scope of this dissertation, improvement of the initial solution has a significant impact on the quality of improvement heuristics, and is therefore a valuable contribution.

[发布机构] University of Pretoria