The Vehicle Allocation Problem: Alternative Formulation and Branch-and-Price Method

The Vehicle Allocation Problem: Alternative Formulation and Branch-and-Price Method. Cruz, C. A., Costa, A. M., Munari, P., & Morabito, R. Computers and Operations Research, 2022.
abstract bibtex

The Vehicle Allocation Problem (VAP) consists of repositioning empty vehicles acrossa set of terminals over a given planning horizon so as to maximize the profitsgenerated from serving demand for transportation of goods between pair of terminals.This problem has been classically modeled using an extended spacetime networkwhich captures the staging of the decision-making process. The present paperproposes a new mixed-integer programming (ILP) model based on the idea ofrepresenting the demands to be met as nodes on a graph. We also derive a Dantzig-Wolfe reformulation which is solved with a branch-and-price (BP) method. Theproposed BP uses a stabilized interior-point column generation approach anda branching procedure that imposes constraints in the master problem, thus notdamaging the structure of the subproblems. Additionally, we show that thesesubproblems can be solved efficiently using a shortest path algorithm on a directedacyclic graphs. Computational results are carried out on a realistic-sizedbenchmark instances, commonly used in the literature. The results show the efficacy ofthe proposed strategies. In particular, the BP method solved the whole set of instancesto proven optimality for the first time and in faster competitive times.

@article{cruzvehicle,
  title = {The Vehicle Allocation Problem: Alternative Formulation and Branch-and-Price Method},
  author = {Cruz, C. A. and Costa, A. M. and Munari, P. and Morabito, R.},
  year = {2022},
  journal = {Computers and Operations Research},
  volume = {144},
  abstract = {The Vehicle Allocation Problem (VAP) consists of repositioning empty vehicles acrossa set of terminals over a given planning horizon so as to maximize the profitsgenerated from serving demand for transportation of goods between pair of terminals.This problem has been classically modeled using an extended spacetime networkwhich captures the staging of the decision-making process. The present paperproposes a new mixed-integer programming (ILP) model based on the idea ofrepresenting the demands to be met as nodes on a graph. We also derive a Dantzig-Wolfe reformulation which is solved with a branch-and-price (BP) method. Theproposed BP uses a stabilized interior-point column generation approach anda branching procedure that imposes constraints in the master problem, thus notdamaging the structure of the subproblems. Additionally, we show that thesesubproblems can be solved efficiently using a shortest path algorithm on a directedacyclic graphs. Computational results are carried out on a realistic-sizedbenchmark instances, commonly used in the literature. The results show the efficacy ofthe proposed strategies. In particular, the BP method solved the whole set of instancesto proven optimality for the first time and in faster competitive times.}
}

Downloads: 0

{"_id":"XdQgtnCWPRix5uT63","bibbaseid":"cruz-costa-munari-morabito-thevehicleallocationproblemalternativeformulationandbranchandpricemethod-2022","author_short":["Cruz, C. A.","Costa, A. M.","Munari, P.","Morabito, R."],"bibdata":{"bibtype":"article","type":"article","title":"The Vehicle Allocation Problem: Alternative Formulation and Branch-and-Price Method","author":[{"propositions":[],"lastnames":["Cruz"],"firstnames":["C.","A."],"suffixes":[]},{"propositions":[],"lastnames":["Costa"],"firstnames":["A.","M."],"suffixes":[]},{"propositions":[],"lastnames":["Munari"],"firstnames":["P."],"suffixes":[]},{"propositions":[],"lastnames":["Morabito"],"firstnames":["R."],"suffixes":[]}],"year":"2022","journal":"Computers and Operations Research","volume":"144","abstract":"The Vehicle Allocation Problem (VAP) consists of repositioning empty vehicles acrossa set of terminals over a given planning horizon so as to maximize the profitsgenerated from serving demand for transportation of goods between pair of terminals.This problem has been classically modeled using an extended spacetime networkwhich captures the staging of the decision-making process. The present paperproposes a new mixed-integer programming (ILP) model based on the idea ofrepresenting the demands to be met as nodes on a graph. We also derive a Dantzig-Wolfe reformulation which is solved with a branch-and-price (BP) method. Theproposed BP uses a stabilized interior-point column generation approach anda branching procedure that imposes constraints in the master problem, thus notdamaging the structure of the subproblems. Additionally, we show that thesesubproblems can be solved efficiently using a shortest path algorithm on a directedacyclic graphs. Computational results are carried out on a realistic-sizedbenchmark instances, commonly used in the literature. The results show the efficacy ofthe proposed strategies. In particular, the BP method solved the whole set of instancesto proven optimality for the first time and in faster competitive times.","bibtex":"@article{cruzvehicle,\n title = {The Vehicle Allocation Problem: Alternative Formulation and Branch-and-Price Method},\n author = {Cruz, C. A. and Costa, A. M. and Munari, P. and Morabito, R.},\n year = {2022},\n journal = {Computers and Operations Research},\n volume = {144},\n abstract = {The Vehicle Allocation Problem (VAP) consists of repositioning empty vehicles acrossa set of terminals over a given planning horizon so as to maximize the profitsgenerated from serving demand for transportation of goods between pair of terminals.This problem has been classically modeled using an extended spacetime networkwhich captures the staging of the decision-making process. The present paperproposes a new mixed-integer programming (ILP) model based on the idea ofrepresenting the demands to be met as nodes on a graph. We also derive a Dantzig-Wolfe reformulation which is solved with a branch-and-price (BP) method. Theproposed BP uses a stabilized interior-point column generation approach anda branching procedure that imposes constraints in the master problem, thus notdamaging the structure of the subproblems. Additionally, we show that thesesubproblems can be solved efficiently using a shortest path algorithm on a directedacyclic graphs. Computational results are carried out on a realistic-sizedbenchmark instances, commonly used in the literature. The results show the efficacy ofthe proposed strategies. In particular, the BP method solved the whole set of instancesto proven optimality for the first time and in faster competitive times.}\n}\n\n","author_short":["Cruz, C. A.","Costa, A. M.","Munari, P.","Morabito, R."],"key":"cruzvehicle","id":"cruzvehicle","bibbaseid":"cruz-costa-munari-morabito-thevehicleallocationproblemalternativeformulationandbranchandpricemethod-2022","role":"author","urls":{},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://www.dropbox.com/s/6qxz2tlaz2bi6av/costaam.bib?dl=1","dataSources":["MrfAAeH3CCWrgiXCu"],"keywords":[],"search_terms":["vehicle","allocation","problem","alternative","formulation","branch","price","method","cruz","costa","munari","morabito"],"title":"The Vehicle Allocation Problem: Alternative Formulation and Branch-and-Price Method","year":2022}