TY - JOUR
T1 - The distance constrained multiple vehicle traveling purchaser problem
AU - Bianchessi, N.
AU - Mansini, R.
AU - Speranza, M. G.
PY - 2014/5/16
Y1 - 2014/5/16
N2 - 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.
AB - 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.
KW - Branch-and-price
KW - Column generation
KW - Distance constraint
KW - Formulations
KW - Multiple vehicle traveling purchaser problem
UR - http://www.scopus.com/inward/record.url?scp=84893219661&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893219661&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2013.10.018
DO - 10.1016/j.ejor.2013.10.018
M3 - Article
AN - SCOPUS:84893219661
VL - 235
SP - 73
EP - 87
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -