The distance constrained multiple vehicle traveling purchaser problem |
| |
Authors: | N. Bianchessi R. Mansini M.G. Speranza |
| |
Affiliation: | 1. Department of Information Engineering, University of Brescia, Italy;2. Department of Economics and Management, University of Brescia, Italy |
| |
Abstract: | In the Distance Constrained Multiple Vehicle Traveling Purchaser Problem (DC-MVTPP) a fleet of vehicles is available to visit suppliers offering products at different prices and with different quantity availabilities. The DC-MVTPP consists in selecting a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while ensuring that the distance traveled by each vehicle does not exceed a predefined upper bound. The problem generalizes the classical Traveling Purchaser Problem (TPP) and adds new realistic features to the decision problem. In this paper we present different mathematical programming formulations for the problem. A branch-and-price algorithm is also proposed to solve a set partitioning formulation where columns represent feasible routes for the vehicles. At each node of the branch-and-bound tree, the linear relaxation of the set partitioning formulation, augmented by the branching constraints, is solved through column generation. The pricing problem is solved using dynamic programming. A set of instances has been derived from benchmark instances for the asymmetric TPP. Instances with up to 100 suppliers and 200 products have been solved to optimality. |
| |
Keywords: | Multiple vehicle traveling purchaser problem Distance constraint Formulations Branch-and-price Column generation |
本文献已被 ScienceDirect 等数据库收录! |