Industrial and tramp ship routing problems: Closing the gap for real-scale instances. Homsi, G., Martinelli, R., Vidal, T., & Fagerholt, K. European Journal of Operational Research, 283:972–990, 2020.
Paper doi abstract bibtex 2 downloads Recent studies in maritime logistics have introduced a general ship routing problem and a bench- mark suite based on real shipping segments, considering pickups and deliveries, cargo selection, ship- dependent starting locations, travel times and costs, time windows, and incompatibility constraints, among other features. Together, these characteristics pose considerable challenges for exact and heuristic methods, and some cases with as few as 18 cargoes remain unsolved. To face this challenge, we propose an exact branch-and-price (B&P) algorithm and a hybrid metaheuristic. Our exact method generates ele- mentary routes, but exploits decremental state-space relaxation to speed up column generation, heuris- tic strong branching, as well as advanced preprocessing and route enumeration techniques. Our meta- heuristic is a sophisticated extension of the unified hybrid genetic search. It exploits a set-partitioning phase and uses problem-tailored variation operators to efficiently handle all the problem characteristics. As shown in our experimental analyses, the B&P optimally solves 239/240 existing instances within one hour. Scalability experiments on even larger problems demonstrate that it can optimally solve problems with around 60 ships and 200 cargoes (i.e., 400 pickup and delivery services) and find optimality gaps below 1.04% on the largest cases with up to 260 cargoes. The hybrid metaheuristic outperforms all pre- vious heuristics and produces near-optimal solutions within minutes. These results are noteworthy, since these instances are comparable in size with the largest problems routinely solved by shipping companies.
@article{Homsi2019,
abstract = {Recent studies in maritime logistics have introduced a general ship routing problem and a bench- mark suite based on real shipping segments, considering pickups and deliveries, cargo selection, ship- dependent starting locations, travel times and costs, time windows, and incompatibility constraints, among other features. Together, these characteristics pose considerable challenges for exact and heuristic methods, and some cases with as few as 18 cargoes remain unsolved. To face this challenge, we propose an exact branch-and-price (B{\&}P) algorithm and a hybrid metaheuristic. Our exact method generates ele- mentary routes, but exploits decremental state-space relaxation to speed up column generation, heuris- tic strong branching, as well as advanced preprocessing and route enumeration techniques. Our meta- heuristic is a sophisticated extension of the unified hybrid genetic search. It exploits a set-partitioning phase and uses problem-tailored variation operators to efficiently handle all the problem characteristics. As shown in our experimental analyses, the B{\&}P optimally solves 239/240 existing instances within one hour. Scalability experiments on even larger problems demonstrate that it can optimally solve problems with around 60 ships and 200 cargoes (i.e., 400 pickup and delivery services) and find optimality gaps below 1.04{\%} on the largest cases with up to 260 cargoes. The hybrid metaheuristic outperforms all pre- vious heuristics and produces near-optimal solutions within minutes. These results are noteworthy, since these instances are comparable in size with the largest problems routinely solved by shipping companies.},
author = {Homsi, G. and Martinelli, R. and Vidal, T. and Fagerholt, K.},
doi = {10.1016/j.ejor.2019.11.068},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Homsi et al/Homsi et al. - 2020 - Industrial and tramp ship routing problems Closing the gap for real-scale instances(2).pdf:pdf},
journal = {European Journal of Operational Research},
pages = {972--990},
title = {{Industrial and tramp ship routing problems: Closing the gap for real-scale instances}},
url = {https://arxiv.org/pdf/1809.10584.pdf},
volume = {283},
year = {2020}
}
Downloads: 2
{"_id":"66XKXGfEkHYKupC7F","bibbaseid":"homsi-martinelli-vidal-fagerholt-industrialandtrampshiproutingproblemsclosingthegapforrealscaleinstances-2020","authorIDs":["22qDSn3MhX9SE4QdJ","3yYf56wRPnWkN3Smu","3ynfnu9dzwCpjFyP8","4Cqr7mXmuwMcqmZgp","4LBfmwfTjMaiaWZGp","4h7RQtjm26FN2JHmm","5CGJTxHpzSPzfjCzW","6WaMPc3WMEYRf7aPs","6cETYuzEQYR8retFE","73FqktCgC2KRA2tAD","77tduPzfw3m3JNLL6","7A4HJ6DsPznXh7sve","85SGCBAgyjBo8EqhX","8RrxAppjhLH77rYBj","8mYe662FHks9DGP85","9Z6sLhM7Nf8JZW73M","9jZjeCWjPWp9GPhLZ","AQi5akoC7Gjoyos7P","BefrwkyiR8J7BpH2P","BgyqbABx82ccGwh7u","CHtRiPZPkRwY2Zj7P","CJsebKwmHZXfYfMjo","CPLtxLfbnrfQSHGiB","CjLc4EpPxRncABnnr","DLXuK3bF2C2gr44vp","DPRDMkXjBidpi4TDy","EB5vie87D5rRFQRhH","FDhjZxCHhq2XiFeZ2","GSx5d2F7X439yA2yB","GwDyrbRR6A99TwkQC","Hc4Gb76fWgRBHmdb9","Jq73HtWDoKQ3JAwWo","KB5iWzr6nWj8bhRbP","Koq8bRcrKQiGCJQ68","L2iNP5AjTduSscwoZ","Lak6KrCQjwkDWRTjG","M6ki37ZgE3yNsAfkL","MiMQgwyyJwJtxDBvk","MwBJWB9CH2kRd7DSa","NsK8HbdNJ7HrJ4CWt","R9evTLxzdqHJ6gg56","RDcEjnEuS49kyJbq7","Ru7stmEDSYkhFjtfB","WQuu6QAQ4uygwgjJj","XJsoGYbpczCFkxyff","XPZWQtjJms9WJenoJ","Y6ecKF4QK6uxEeD9a","a6uiXNEZFSTrwZqxY","awoTsndRPACdYbwLY","bJENH3RRYCbXdmWai","ehJ7KjD2Aqb9Efd6v","fsKEgFS3pySqRFdMc","gjjADg9JGSWhj8qbx","gxRgZbcdc2KFBF2o6","hsaFAvcArcu6EBHjb","iLPFjodLsRfo6uhmu","iX5PbZ3cMwgEWwC2k","jg9mQ5WtEN5o4kBZG","jxdbCYtZMzy4EdpP5","mXJzPLn7g897B6cRE","mo3mdPgNy6xeyHTTw","nEaHJmLgCx2WtmFji","nHPSALCyaatA3Mgbv","o63vPZA3v7dSNBwsb","oD9oSutzwynEe9NXj","oijLT2TDpdc9T2CA5","sYrkHzi2HZP2SDK7k","sjyTppdABxdRywBvL","suy82rpLS7tJ6H6Bw","t2dQWQPFqMuvbZaWa","ta4Ded5yZwWqpNab2","trPFdvK4jZKXXFfyZ","uLHCaJrHCX3XMyF8o","uyCNkc8aT5C6evZJD","voCzhan7GbpJ2Xg7n","vsedCHjb2BzDhg3oC","wRbdKdQfwW38tKHrD","xMCrLWJ5bnK4scREL","xxR6RTsWFRB3CNo8r","ztt88xLAbCEz33TEh"],"author_short":["Homsi, G.","Martinelli, R.","Vidal, T.","Fagerholt, K."],"bibdata":{"bibtype":"article","type":"article","abstract":"Recent studies in maritime logistics have introduced a general ship routing problem and a bench- mark suite based on real shipping segments, considering pickups and deliveries, cargo selection, ship- dependent starting locations, travel times and costs, time windows, and incompatibility constraints, among other features. Together, these characteristics pose considerable challenges for exact and heuristic methods, and some cases with as few as 18 cargoes remain unsolved. To face this challenge, we propose an exact branch-and-price (B&P) algorithm and a hybrid metaheuristic. Our exact method generates ele- mentary routes, but exploits decremental state-space relaxation to speed up column generation, heuris- tic strong branching, as well as advanced preprocessing and route enumeration techniques. Our meta- heuristic is a sophisticated extension of the unified hybrid genetic search. It exploits a set-partitioning phase and uses problem-tailored variation operators to efficiently handle all the problem characteristics. As shown in our experimental analyses, the B&P optimally solves 239/240 existing instances within one hour. Scalability experiments on even larger problems demonstrate that it can optimally solve problems with around 60 ships and 200 cargoes (i.e., 400 pickup and delivery services) and find optimality gaps below 1.04% on the largest cases with up to 260 cargoes. The hybrid metaheuristic outperforms all pre- vious heuristics and produces near-optimal solutions within minutes. These results are noteworthy, since these instances are comparable in size with the largest problems routinely solved by shipping companies.","author":[{"propositions":[],"lastnames":["Homsi"],"firstnames":["G."],"suffixes":[]},{"propositions":[],"lastnames":["Martinelli"],"firstnames":["R."],"suffixes":[]},{"propositions":[],"lastnames":["Vidal"],"firstnames":["T."],"suffixes":[]},{"propositions":[],"lastnames":["Fagerholt"],"firstnames":["K."],"suffixes":[]}],"doi":"10.1016/j.ejor.2019.11.068","file":":C$\\$:/Users/Thibaut/Documents/Mendeley-Articles/Homsi et al/Homsi et al. - 2020 - Industrial and tramp ship routing problems Closing the gap for real-scale instances(2).pdf:pdf","journal":"European Journal of Operational Research","pages":"972–990","title":"Industrial and tramp ship routing problems: Closing the gap for real-scale instances","url":"https://arxiv.org/pdf/1809.10584.pdf","volume":"283","year":"2020","bibtex":"@article{Homsi2019,\nabstract = {Recent studies in maritime logistics have introduced a general ship routing problem and a bench- mark suite based on real shipping segments, considering pickups and deliveries, cargo selection, ship- dependent starting locations, travel times and costs, time windows, and incompatibility constraints, among other features. Together, these characteristics pose considerable challenges for exact and heuristic methods, and some cases with as few as 18 cargoes remain unsolved. To face this challenge, we propose an exact branch-and-price (B{\\&}P) algorithm and a hybrid metaheuristic. Our exact method generates ele- mentary routes, but exploits decremental state-space relaxation to speed up column generation, heuris- tic strong branching, as well as advanced preprocessing and route enumeration techniques. Our meta- heuristic is a sophisticated extension of the unified hybrid genetic search. It exploits a set-partitioning phase and uses problem-tailored variation operators to efficiently handle all the problem characteristics. As shown in our experimental analyses, the B{\\&}P optimally solves 239/240 existing instances within one hour. Scalability experiments on even larger problems demonstrate that it can optimally solve problems with around 60 ships and 200 cargoes (i.e., 400 pickup and delivery services) and find optimality gaps below 1.04{\\%} on the largest cases with up to 260 cargoes. The hybrid metaheuristic outperforms all pre- vious heuristics and produces near-optimal solutions within minutes. These results are noteworthy, since these instances are comparable in size with the largest problems routinely solved by shipping companies.},\nauthor = {Homsi, G. and Martinelli, R. and Vidal, T. and Fagerholt, K.},\ndoi = {10.1016/j.ejor.2019.11.068},\nfile = {:C$\\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Homsi et al/Homsi et al. - 2020 - Industrial and tramp ship routing problems Closing the gap for real-scale instances(2).pdf:pdf},\njournal = {European Journal of Operational Research},\npages = {972--990},\ntitle = {{Industrial and tramp ship routing problems: Closing the gap for real-scale instances}},\nurl = {https://arxiv.org/pdf/1809.10584.pdf},\nvolume = {283},\nyear = {2020}\n}\n","author_short":["Homsi, G.","Martinelli, R.","Vidal, T.","Fagerholt, K."],"key":"Homsi2019","id":"Homsi2019","bibbaseid":"homsi-martinelli-vidal-fagerholt-industrialandtrampshiproutingproblemsclosingthegapforrealscaleinstances-2020","role":"author","urls":{"Paper":"https://arxiv.org/pdf/1809.10584.pdf"},"metadata":{"authorlinks":{"vidal, t":"https://bibbase.org/show?bib=https%3A%2F%2Fw1.cirrelt.ca%2F%7Evidalt%2Fresources%2FMy%2520Collection.bib"}},"downloads":2,"html":""},"bibtype":"article","biburl":"https://w1.cirrelt.ca/~vidalt/resources/My Collection.bib","creationDate":"2020-04-28T21:05:51.091Z","downloads":2,"keywords":[],"search_terms":["industrial","tramp","ship","routing","problems","closing","gap","real","scale","instances","homsi","martinelli","vidal","fagerholt"],"title":"Industrial and tramp ship routing problems: Closing the gap for real-scale instances","year":2020,"dataSources":["yinfondEAJRbDM9sJ","sempRA6PhmAdGk3yG"]}