Fast validation of time windows in a routing problemSolving ATSP problem for large-scale problemIs there a canonical name for Score Folding (multiplying a priority soft constraint by a big weight)?How to handle real-world (soft) constraints in an optimization problem?Capacitated VRP-TW: Gehring & Homberger instances
String manipulation with std::adjacent_find
Does the Pole of Angling's command word require an action?
LED glows slightly during soldering
Is English unusual in having no second person plural form?
What is the measurable difference between dry basil and fresh?
Was I subtly told to resign?
Why weren't bootable game disks ever common on the IBM PC?
Confirming the Identity of a (Friendly) Reviewer After the Reviews
Is a request to book a business flight ticket for a graduate student an unreasonable one?
How can I get a player to accept that they should stop trying to pull stunts without thinking them through first?
What specific instant in time in the MCU has been depicted the most times?
What's the point of having a RAID 1 configuration over incremental backups to a secondary drive?
How would vampires avoid contracting diseases?
How can I fix the dull colors I am getting in Ubuntu 19.04 Terminal?
What does the phrase "head down the rat's hole" mean here?
How to say "How long have you had this dream?"
How do you move up one folder in Finder?
Is it OK to leave real names & info visible in business card portfolio?
Are there any sports for which the world's best player is female?
What happens to unproductive professors?
Optimization terminology: "Exact" v. "Approximate"
Is "I do not want you to go nowhere" a case of "DOUBLE-NEGATIVES" as claimed by Grammarly?
Is there any reason why MCU changed the Snap to Blip
What is this little owl-like bird?
Fast validation of time windows in a routing problem
Solving ATSP problem for large-scale problemIs there a canonical name for Score Folding (multiplying a priority soft constraint by a big weight)?How to handle real-world (soft) constraints in an optimization problem?Capacitated VRP-TW: Gehring & Homberger instances
$begingroup$
When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any procedure would require this verification in the route generation process. Are there computational (or numerical or mathematical) tricks to perform this constraint verification quickly for a given route (sequence of nodes)? In particular (and this is the harder case) when you can't wait until the time window starts (meaning, can't arrive way too early to a location).
constraint vehicle-routing
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any procedure would require this verification in the route generation process. Are there computational (or numerical or mathematical) tricks to perform this constraint verification quickly for a given route (sequence of nodes)? In particular (and this is the harder case) when you can't wait until the time window starts (meaning, can't arrive way too early to a location).
constraint vehicle-routing
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any procedure would require this verification in the route generation process. Are there computational (or numerical or mathematical) tricks to perform this constraint verification quickly for a given route (sequence of nodes)? In particular (and this is the harder case) when you can't wait until the time window starts (meaning, can't arrive way too early to a location).
constraint vehicle-routing
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any procedure would require this verification in the route generation process. Are there computational (or numerical or mathematical) tricks to perform this constraint verification quickly for a given route (sequence of nodes)? In particular (and this is the harder case) when you can't wait until the time window starts (meaning, can't arrive way too early to a location).
constraint vehicle-routing
constraint vehicle-routing
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
edited 9 hours ago
LarrySnyder610
3,7439 silver badges51 bronze badges
3,7439 silver badges51 bronze badges
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
asked 9 hours ago
Daniel DuqueDaniel Duque
3267 bronze badges
3267 bronze badges
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Daniel Duque is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route.
However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article by T Vidal et al on the subject.
Best
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
$endgroup$
$begingroup$
Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2).
$endgroup$
– Kevin Dalmeijer
4 hours ago
add a comment |
$begingroup$
The standard slack time calculation used by various authors takes the last stop in a route (which could be the 'depot' stop), works out the latest feasible time it can be served without breaking its time window, and then propagates this 'latest feasible time' backwards in the route (i.e. to the stop before, the stop before that etc). The back propagation calculation uses open time, travel time etc. Each time it propagates this 'latest feasible time' backwards, it takes the min of 'latest feasible time' from the stops later in the route and the current stop. The result is that for each stop, you get the latest feasible time it can be served without breaking its time window constraint or those later in the route.
Regarding not being able to wait until the time window starts, I'm guessing - but haven't proved mathematically - that you could use this methodology but for each stop calculate the 'earliest feasible time' it can be served instead and when you back propagate, take the max of 'earliest feasible time' instead? You'd presumably only use this 'earliest feasible time' if you're removing or swapping a stop in a route though?
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Daniel Duque is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f939%2ffast-validation-of-time-windows-in-a-routing-problem%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route.
However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article by T Vidal et al on the subject.
Best
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
$endgroup$
$begingroup$
Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2).
$endgroup$
– Kevin Dalmeijer
4 hours ago
add a comment |
$begingroup$
Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route.
However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article by T Vidal et al on the subject.
Best
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
$endgroup$
$begingroup$
Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2).
$endgroup$
– Kevin Dalmeijer
4 hours ago
add a comment |
$begingroup$
Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route.
However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article by T Vidal et al on the subject.
Best
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
$endgroup$
Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route.
However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article by T Vidal et al on the subject.
Best
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
answered 8 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
6261 silver badge6 bronze badges
$begingroup$
Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2).
$endgroup$
– Kevin Dalmeijer
4 hours ago
add a comment |
$begingroup$
Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2).
$endgroup$
– Kevin Dalmeijer
4 hours ago
$begingroup$
Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2).
$endgroup$
– Kevin Dalmeijer
4 hours ago
$begingroup$
Visser, T.R. & Spliet, R. (2017). Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems. Econometric Institute Research Papers, EI2017-23, may also be a useful reference. The main focus of this paper is on time-dependent travel times, but results for the not time-dependent case are also stated (e.g., see Tables 1 and 2).
$endgroup$
– Kevin Dalmeijer
4 hours ago
add a comment |
$begingroup$
The standard slack time calculation used by various authors takes the last stop in a route (which could be the 'depot' stop), works out the latest feasible time it can be served without breaking its time window, and then propagates this 'latest feasible time' backwards in the route (i.e. to the stop before, the stop before that etc). The back propagation calculation uses open time, travel time etc. Each time it propagates this 'latest feasible time' backwards, it takes the min of 'latest feasible time' from the stops later in the route and the current stop. The result is that for each stop, you get the latest feasible time it can be served without breaking its time window constraint or those later in the route.
Regarding not being able to wait until the time window starts, I'm guessing - but haven't proved mathematically - that you could use this methodology but for each stop calculate the 'earliest feasible time' it can be served instead and when you back propagate, take the max of 'earliest feasible time' instead? You'd presumably only use this 'earliest feasible time' if you're removing or swapping a stop in a route though?
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
The standard slack time calculation used by various authors takes the last stop in a route (which could be the 'depot' stop), works out the latest feasible time it can be served without breaking its time window, and then propagates this 'latest feasible time' backwards in the route (i.e. to the stop before, the stop before that etc). The back propagation calculation uses open time, travel time etc. Each time it propagates this 'latest feasible time' backwards, it takes the min of 'latest feasible time' from the stops later in the route and the current stop. The result is that for each stop, you get the latest feasible time it can be served without breaking its time window constraint or those later in the route.
Regarding not being able to wait until the time window starts, I'm guessing - but haven't proved mathematically - that you could use this methodology but for each stop calculate the 'earliest feasible time' it can be served instead and when you back propagate, take the max of 'earliest feasible time' instead? You'd presumably only use this 'earliest feasible time' if you're removing or swapping a stop in a route though?
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
The standard slack time calculation used by various authors takes the last stop in a route (which could be the 'depot' stop), works out the latest feasible time it can be served without breaking its time window, and then propagates this 'latest feasible time' backwards in the route (i.e. to the stop before, the stop before that etc). The back propagation calculation uses open time, travel time etc. Each time it propagates this 'latest feasible time' backwards, it takes the min of 'latest feasible time' from the stops later in the route and the current stop. The result is that for each stop, you get the latest feasible time it can be served without breaking its time window constraint or those later in the route.
Regarding not being able to wait until the time window starts, I'm guessing - but haven't proved mathematically - that you could use this methodology but for each stop calculate the 'earliest feasible time' it can be served instead and when you back propagate, take the max of 'earliest feasible time' instead? You'd presumably only use this 'earliest feasible time' if you're removing or swapping a stop in a route though?
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
The standard slack time calculation used by various authors takes the last stop in a route (which could be the 'depot' stop), works out the latest feasible time it can be served without breaking its time window, and then propagates this 'latest feasible time' backwards in the route (i.e. to the stop before, the stop before that etc). The back propagation calculation uses open time, travel time etc. Each time it propagates this 'latest feasible time' backwards, it takes the min of 'latest feasible time' from the stops later in the route and the current stop. The result is that for each stop, you get the latest feasible time it can be served without breaking its time window constraint or those later in the route.
Regarding not being able to wait until the time window starts, I'm guessing - but haven't proved mathematically - that you could use this methodology but for each stop calculate the 'earliest feasible time' it can be served instead and when you back propagate, take the max of 'earliest feasible time' instead? You'd presumably only use this 'earliest feasible time' if you're removing or swapping a stop in a route though?
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
answered 2 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
1134 bronze badges
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Open Door Logistics is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
Daniel Duque is a new contributor. Be nice, and check out our Code of Conduct.
Daniel Duque is a new contributor. Be nice, and check out our Code of Conduct.
Daniel Duque is a new contributor. Be nice, and check out our Code of Conduct.
Daniel Duque is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Operations Research Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f939%2ffast-validation-of-time-windows-in-a-routing-problem%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
