Fast validation of time windows in a routing problemSolving ATSP problem for large-scale problemIs there a...
Does throwing a penny at a train stop the train?
Was I subtly told to resign?
How can a dictatorship government be beneficial to a dictator in a post-scarcity society?
Confirming the Identity of a (Friendly) Reviewer After the Reviews
RPI3B+: What are the four components below the HDMI connector called?
How can I fix the dull colors I am getting in Ubuntu 19.04 Terminal?
Is there any word for "disobedience to God"?
Is it possible to create a craft with specific bones, like the bones of a forgotten beast?
Why weren't bootable game disks ever common on the IBM PC?
What specific instant in time in the MCU has been depicted the most times?
Are there any balance issues in allowing two half-feats to be taken without the Ability Score Increase instead of a feat?
What to do with a rabbit in a survival situation?
Why isn't pressure filtration popular compared to vacuum filtration?
Switching interface VLAN ID Mid-Production
How to trigger Authentification of Named Credential created via Apex
How can I get a player to accept that they should stop trying to pull stunts without thinking them through first?
How do native German speakers usually express skepticism (using even) about a premise?
What's the point of having a RAID 1 configuration over incremental backups to a secondary drive?
OR-backed serious games
What is the measurable difference between dry basil and fresh?
Word meaning to destroy books
Graduate student with abysmal English writing skills, how to help
How were Martello towers supposed to work?
This one's for Matthew:
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 9 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
5 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 3 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 9 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
5 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 9 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
5 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 9 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 9 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
answered 9 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
answered 9 hours ago
Claudio ContardoClaudio Contardo
6261 silver badge6 bronze badges
answered 9 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
5 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
5 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
5 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
5 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 3 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 3 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 3 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 3 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 3 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 3 hours ago
Open Door LogisticsOpen Door Logistics
1134 bronze badges
answered 3 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
