Jan Fábry
Katedra ekonometrie
Fakulta informatiky a statistiky
Abstrakt
Pickup and Delivery Problems are special instances of Vehicle Routing Problems. In Transshipment Problem, homogenous goods are transported between nodes through arcs with limited capacity. The objective is to satisfy requirements of customers without exceeding capacities of suppliers and minimize total transportation cost. Container version consists in the transport of goods in capacitated containers; cost per container is defined for each arc. In Messenger Problem, a shipment is given by the pickup location and delivery location. Because shipment sizes are obviously given, vehicle capacity has to be considered. In such case multiple vehicles must be used. In addition, time windows can be introduced in the form of the earliest possible time for pickup and the latest possible time for delivery. Because NP-hard problems are solved, it is necessary to use heuristic algorithms for real applications, e.g. simple modifications of nearest neighbor method and insertion method. Generated routes can be improved using the modified exchange algorithm.
