Vehicle Minimization for the Multimodal Pickup and Delivery Problem with Time Windows.

摘要

The algorithm proposed here is used for heuristic solutions for the Multimodal Multiple Vehicle Routing Problem with Unloading Capacity, Pickup and Dropoff, and Time Windows, solved so as to minimize the number of vehicles used, subject to varying objective function values for each vehicle. The MVRP is simplified and split into a routing problem and a scheduling problem. The routing problem is addressed by Dijkstra's Algorithm. This generates a new network for the second stage of the algorithm. It is assumed that the shortest path is the correct path to use, and shipments each travel unimodally. The scheduling problem is addressed by treating the various paths as though they were machines, with vehicle number being treated approximately as capacity for the machines, and unloading capacity being treated as a second stage in the processing. The problem is analyzed by assigning all shipments which can be assigned elsewhere away from the most expensive mode and then assigning only leftover shipments to the most expensive mode. Multiple resolutions of the scheduling problem result in feasible solutions for less expensive modes, which results in a feasible solution for every mode, and a low cost solution in terms of vehicles used.