Time-window relaxations in vehicle routing heuristics. Vidal, T., Crainic, T., Gendreau, M., & Prins, C. Journal of Heuristics, 21(3):329–358, 2015.
Paper doi abstract bibtex 2 downloads The contribution of infeasible solutions in heuristic searches for vehicle routing problems (VRP) is not a subject of consensus in the metaheuristics community. Infeasible solutions may allow transitioning between structurally different feasible solutions, thus enhancing the search, but they also lead to more complex move-evaluation procedures and wider search spaces. This paper introduces an experimental assessment of the impact of infeasible solutions on heuristic searches, through various empirical studies on local improvement procedures, iterated local searches, and hybrid genetic algorithms for the VRP with time windows and other related variants with fleet mix, backhauls, and multiple periods. Four relaxation schemes are considered, allowing penalized late arrivals to customers, early and late arrivals, returns in time, or a flexible travel time relaxation. For all considered problems and methods, our experiments demonstrate the significant positive impact of penalized infeasible solution. Differences can also be observed between individual relaxation schemes. The “returns in time” and “flexible travel time” relaxations appear as the best options in terms of solution quality, CPU time, and scalability.
@article{Vidal2013a,
abstract = {The contribution of infeasible solutions in heuristic searches for vehicle routing problems (VRP) is not a subject of consensus in the metaheuristics community. Infeasible solutions may allow transitioning between structurally different feasible solutions, thus enhancing the search, but they also lead to more complex move-evaluation procedures and wider search spaces. This paper introduces an experimental assessment of the impact of infeasible solutions on heuristic searches, through various empirical studies on local improvement procedures, iterated local searches, and hybrid genetic algorithms for the VRP with time windows and other related variants with fleet mix, backhauls, and multiple periods. Four relaxation schemes are considered, allowing penalized late arrivals to customers, early and late arrivals, returns in time, or a flexible travel time relaxation. For all considered problems and methods, our experiments demonstrate the significant positive impact of penalized infeasible solution. Differences can also be observed between individual relaxation schemes. The “returns in time” and “flexible travel time” relaxations appear as the best options in terms of solution quality, CPU time, and scalability.},
author = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.},
doi = {10.1007/s10732-014-9273-y},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2015 - Time-window relaxations in vehicle routing heuristics.pdf:pdf},
journal = {Journal of Heuristics},
number = {3},
pages = {329--358},
title = {{Time-window relaxations in vehicle routing heuristics}},
url = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2013-43.pdf},
volume = {21},
year = {2015}
}
Downloads: 2
{"_id":"jWjuo5wRhEiLzwnaA","bibbaseid":"vidal-crainic-gendreau-prins-timewindowrelaxationsinvehicleroutingheuristics-2015","downloads":2,"creationDate":"2017-06-20T13:26:52.942Z","title":"Time-window relaxations in vehicle routing heuristics","author_short":["Vidal, T.","Crainic, T.","Gendreau, M.","Prins, C."],"year":2015,"bibtype":"article","biburl":"https://w1.cirrelt.ca/~vidalt/resources/My Collection.bib","bibdata":{"bibtype":"article","type":"article","abstract":"The contribution of infeasible solutions in heuristic searches for vehicle routing problems (VRP) is not a subject of consensus in the metaheuristics community. Infeasible solutions may allow transitioning between structurally different feasible solutions, thus enhancing the search, but they also lead to more complex move-evaluation procedures and wider search spaces. This paper introduces an experimental assessment of the impact of infeasible solutions on heuristic searches, through various empirical studies on local improvement procedures, iterated local searches, and hybrid genetic algorithms for the VRP with time windows and other related variants with fleet mix, backhauls, and multiple periods. Four relaxation schemes are considered, allowing penalized late arrivals to customers, early and late arrivals, returns in time, or a flexible travel time relaxation. For all considered problems and methods, our experiments demonstrate the significant positive impact of penalized infeasible solution. Differences can also be observed between individual relaxation schemes. The “returns in time” and “flexible travel time” relaxations appear as the best options in terms of solution quality, CPU time, and scalability.","author":[{"propositions":[],"lastnames":["Vidal"],"firstnames":["T."],"suffixes":[]},{"propositions":[],"lastnames":["Crainic"],"firstnames":["T.G."],"suffixes":[]},{"propositions":[],"lastnames":["Gendreau"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Prins"],"firstnames":["C."],"suffixes":[]}],"doi":"10.1007/s10732-014-9273-y","file":":C$\\$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2015 - Time-window relaxations in vehicle routing heuristics.pdf:pdf","journal":"Journal of Heuristics","number":"3","pages":"329–358","title":"Time-window relaxations in vehicle routing heuristics","url":"https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2013-43.pdf","volume":"21","year":"2015","bibtex":"@article{Vidal2013a,\nabstract = {The contribution of infeasible solutions in heuristic searches for vehicle routing problems (VRP) is not a subject of consensus in the metaheuristics community. Infeasible solutions may allow transitioning between structurally different feasible solutions, thus enhancing the search, but they also lead to more complex move-evaluation procedures and wider search spaces. This paper introduces an experimental assessment of the impact of infeasible solutions on heuristic searches, through various empirical studies on local improvement procedures, iterated local searches, and hybrid genetic algorithms for the VRP with time windows and other related variants with fleet mix, backhauls, and multiple periods. Four relaxation schemes are considered, allowing penalized late arrivals to customers, early and late arrivals, returns in time, or a flexible travel time relaxation. For all considered problems and methods, our experiments demonstrate the significant positive impact of penalized infeasible solution. Differences can also be observed between individual relaxation schemes. The “returns in time” and “flexible travel time” relaxations appear as the best options in terms of solution quality, CPU time, and scalability.},\nauthor = {Vidal, T. and Crainic, T.G. and Gendreau, M. and Prins, C.},\ndoi = {10.1007/s10732-014-9273-y},\nfile = {:C$\\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Vidal et al/Vidal et al. - 2015 - Time-window relaxations in vehicle routing heuristics.pdf:pdf},\njournal = {Journal of Heuristics},\nnumber = {3},\npages = {329--358},\ntitle = {{Time-window relaxations in vehicle routing heuristics}},\nurl = {https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2013-43.pdf},\nvolume = {21},\nyear = {2015}\n}\n","author_short":["Vidal, T.","Crainic, T.","Gendreau, M.","Prins, C."],"key":"Vidal2013a","id":"Vidal2013a","bibbaseid":"vidal-crainic-gendreau-prins-timewindowrelaxationsinvehicleroutingheuristics-2015","role":"author","urls":{"Paper":"https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2013-43.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":""},"search_terms":["time","window","relaxations","vehicle","routing","heuristics","vidal","crainic","gendreau","prins"],"keywords":[],"authorIDs":["22qDSn3MhX9SE4QdJ","2eyrFQa9PCh5a8ea8","39vXMT4DP7K7Xq3aP","3yYf56wRPnWkN3Smu","3ynfnu9dzwCpjFyP8","4Cqr7mXmuwMcqmZgp","4LBfmwfTjMaiaWZGp","4h7RQtjm26FN2JHmm","5949229c25f5fd9d7000003d","5949255825f5fd9d7000004b","5CGJTxHpzSPzfjCzW","5de7abebbc280fdf01000076","5de7d6665e1638de010001f9","5de86a278ff138de0100014d","5dea95b1a71b4bdf0100014d","5dec4d93e16431f20100007b","5df133638fc423de01000199","5df1c8e21070c8ef0100003a","5df6f76fdf3bb9f201000085","5dfa57207d1403df01000026","5dfb19d0f85d64df01000004","5dfb3f97e04f92df0100007e","5dfd53b3991725de0100005a","5e01ffc621cdf8e4010000f1","5e02a17d64e549de01000091","5e0907cd79e131f3010000c7","5e0c109b24223cde01000043","5e0c88d9464605de010000c7","5e10d31b0192c6df010000b7","5e14d212429a53df01000027","5e14f043b46f1bdf0100005c","5e15757a1e2528de010000f8","5e1787e6cf35a4de0100019b","5e191498a7672ede01000136","5e1bb58061cb16df010000b8","5e1c5a47e556c6de0100015d","5e231b5f327a15de01000022","5e232ec8327a15de010000c7","5e23793bba9fb2de0100006f","5e25e56fa6f19fde0100012b","5e27b34528f7a6de0100014d","5e284bcbc4828cde010000b8","5e2895e288416fde01000018","5e28b0ef88416fde01000249","5e2b96caf92538df01000069","5e2f15434557f3de01000051","5e3002375bfc8ede010000e3","5e301fb77e0df1de0100011d","5e35f9c85cd57fde0100012a","5e36e2d6b26a0fde01000036","5e3800a6918d4ede010000c3","5e3c566fc798e0de0100015a","5e3c6a5767788ede010000be","5e3ce3ee5cd237de010000de","5e3d7c5596e576de0100006a","5e3dbff807ca74de01000114","5e3f1f497da304de01000027","5e4048bc668183de010000e1","5e410989f47523de010000a2","5e4161f2a59dc8df01000194","5e438e29639a35de0100009f","5e44200ffdc393de01000154","5e458c3686f11cdf01000140","5e460590a5737fde010000f1","5e480eabd4b913df0100007e","5e49e5e4885ce9df01000030","5e49ff68cc11a8df0100003a","5e4ab3b715f6c7df0100013c","5e4ac8d70d7631de01000082","5e4b0bee332a9bde01000108","5e4b1b96c59ab1f301000073","5e4c1bfc2dc400de0100010d","5e4d19527d0ec8de010000c2","5e4d25f47d0ec8de01000193","5e4ec057d9cddadf010000be","5e4eefc9338acfde01000033","5e4fede9f5b214df0100004f","5e533cc853de8dde01000031","5e538be6c02a31de01000016","5e54548088d190df0100005c","5e54fb7396ed20df01000020","5e56f3297840dfde01000015","5e582d0a1f3fc8de0100004c","5e5983f48049fcde01000094","5e5bfabed49321e0010000ce","5e5e04335c89fadf0100005e","5e5e26241e54a8df010002af","5e5e3439d3955dde01000021","5e5e3dccd3955dde010000c3","5e5f25518ca867de010000cf","5e5f69665766d9df01000011","5e5fdf9f5241b5de0100007f","5e6094a61fc211de010000bf","5e610b8c31c7d3de01000230","5e62bb57cb259cde0100008b","5e664abda77c4ade01000186","5e67a2bbd527f0de01000265","5e67feb9c1fce0de0100009b","5e6944466964dedf010002bd","5e69b3a123ebccde010001ea","5e6a14be38f351de01000097","6WaMPc3WMEYRf7aPs","6cETYuzEQYR8retFE","73FqktCgC2KRA2tAD","77tduPzfw3m3JNLL6","7A4HJ6DsPznXh7sve","85SGCBAgyjBo8EqhX","8RrxAppjhLH77rYBj","8mYe662FHks9DGP85","9Z6sLhM7Nf8JZW73M","9jZjeCWjPWp9GPhLZ","AQi5akoC7Gjoyos7P","BefrwkyiR8J7BpH2P","BgyqbABx82ccGwh7u","BsQpRnmxZAAaM5Dvv","CEofRTEfHXQmYXKmf","CHtRiPZPkRwY2Zj7P","CJsebKwmHZXfYfMjo","CPLtxLfbnrfQSHGiB","CjLc4EpPxRncABnnr","DA2hGTyXJ5QDgZY9P","DLXuK3bF2C2gr44vp","DPRDMkXjBidpi4TDy","EB5vie87D5rRFQRhH","FDhjZxCHhq2XiFeZ2","GSx5d2F7X439yA2yB","GwDyrbRR6A99TwkQC","GySvg6ZigwYkBPRZs","H4XtJC6XB9eB3E6de","Hc4Gb76fWgRBHmdb9","Jq73HtWDoKQ3JAwWo","KB5iWzr6nWj8bhRbP","KdiQQfsPGngvzYnj8","KkA72QCdDyG25v3ja","Koq8bRcrKQiGCJQ68","L2iNP5AjTduSscwoZ","Lak6KrCQjwkDWRTjG","M6ki37ZgE3yNsAfkL","MiMQgwyyJwJtxDBvk","MwBJWB9CH2kRd7DSa","MyM8bFL9PbJnj6xFj","NsK8HbdNJ7HrJ4CWt","NykasPxRbNPkYaFi6","P7tL46FCmpstpzc5G","Q9mdkfHXYB4L73a7z","R9evTLxzdqHJ6gg56","RDcEjnEuS49kyJbq7","RmCCdPrWkPKcvg8aE","Ru7stmEDSYkhFjtfB","SEL27kiy54WCdaK9P","Txq35A3ycpsEHJFEF","WQuu6QAQ4uygwgjJj","XJsoGYbpczCFkxyff","XPZWQtjJms9WJenoJ","XmDEEHxsYeqKxtds5","Y6ecKF4QK6uxEeD9a","Yj6btsirruZaWE6bm","a6uiXNEZFSTrwZqxY","avZwQMkQEEAjz9udR","awoTsndRPACdYbwLY","bJENH3RRYCbXdmWai","e8uLXuJtLro7DMw49","ehJ7KjD2Aqb9Efd6v","fsKEgFS3pySqRFdMc","gM9KMcoXiWZtAj5sY","gjjADg9JGSWhj8qbx","gxRgZbcdc2KFBF2o6","hsaFAvcArcu6EBHjb","iLPFjodLsRfo6uhmu","iX5PbZ3cMwgEWwC2k","jg9mQ5WtEN5o4kBZG","jxdbCYtZMzy4EdpP5","mH28RcRpdPG275rWc","mXJzPLn7g897B6cRE","mo3mdPgNy6xeyHTTw","nEaHJmLgCx2WtmFji","nHPSALCyaatA3Mgbv","ndYtnzwfxuqRuRQLz","o63vPZA3v7dSNBwsb","oD9oSutzwynEe9NXj","oijLT2TDpdc9T2CA5","qxrYJuZmthuQxnpdc","sYrkHzi2HZP2SDK7k","sjyTppdABxdRywBvL","suy82rpLS7tJ6H6Bw","t2dQWQPFqMuvbZaWa","ta4Ded5yZwWqpNab2","trPFdvK4jZKXXFfyZ","uLHCaJrHCX3XMyF8o","uyCNkc8aT5C6evZJD","voCzhan7GbpJ2Xg7n","vsedCHjb2BzDhg3oC","wChRzg6qYmaDdwjK9","wRbdKdQfwW38tKHrD","whTqfamkmDjHode9m","xMCrLWJ5bnK4scREL","xxR6RTsWFRB3CNo8r","ztt88xLAbCEz33TEh"],"dataSources":["yinfondEAJRbDM9sJ","sempRA6PhmAdGk3yG"]}