Cover Image

Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery

In this paper, we present exact methods for solving the Time Dependent Minimum Tour Duration Problem (TD-MTDP) and the Time Dependent Delivery Man Problem (TD-DMP). Both methods are based on a Dynamic Discretization Discovery (DDD) approach for solving the Time Dependent Traveling Salesman Problem w...

Full description

Saved in:
Bibliographic Details
Main Authors: Duc, Minh Vua, Mike, Hewitt, Duc, D.Vuc
Format: Bài trích
Language:English
Published: Elsevier 2022
Subjects:
Traveling salesman problem
Time dependent travel times
Online Access:https://www.sciencedirect.com/science/article/abs/pii/S0377221722000674?via%3Dihub
https://dlib.phenikaa-uni.edu.vn/handle/PNK/5737
https://doi.org/10.1016/j.ejor.2022.01.029
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-5737
record_format dspace
spelling oai:localhost:PNK-57372022-08-17T05:54:52Z Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery Duc, Minh Vua Mike, Hewitt Duc, D.Vuc Traveling salesman problem Time dependent travel times In this paper, we present exact methods for solving the Time Dependent Minimum Tour Duration Problem (TD-MTDP) and the Time Dependent Delivery Man Problem (TD-DMP). Both methods are based on a Dynamic Discretization Discovery (DDD) approach for solving the Time Dependent Traveling Salesman Problem with Time Windows (TD-TSPTW). Unlike the TD-TSPTW, these problems involve objective functions that depend in part on the time at which the vehicle departs the depot. As such, optimizing these problems adds a scheduling dimension to the problem. We present multiple enhancements to the DDD method, including enabling it to dynamically determine which waiting opportunities at the depot to model. With an extensive computational study we demonstrate that the resulting methods outperform all known methods for both the TD-MTDP and TD-DMP on instances taken from the literature 2022-05-05T07:26:15Z 2022-05-05T07:26:15Z 2022 Bài trích https://www.sciencedirect.com/science/article/abs/pii/S0377221722000674?via%3Dihub https://dlib.phenikaa-uni.edu.vn/handle/PNK/5737 https://doi.org/10.1016/j.ejor.2022.01.029 en Elsevier
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic Traveling salesman problem
Time dependent travel times
spellingShingle Traveling salesman problem
Time dependent travel times
Duc, Minh Vua
Mike, Hewitt
Duc, D.Vuc
Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
description In this paper, we present exact methods for solving the Time Dependent Minimum Tour Duration Problem (TD-MTDP) and the Time Dependent Delivery Man Problem (TD-DMP). Both methods are based on a Dynamic Discretization Discovery (DDD) approach for solving the Time Dependent Traveling Salesman Problem with Time Windows (TD-TSPTW). Unlike the TD-TSPTW, these problems involve objective functions that depend in part on the time at which the vehicle departs the depot. As such, optimizing these problems adds a scheduling dimension to the problem. We present multiple enhancements to the DDD method, including enabling it to dynamically determine which waiting opportunities at the depot to model. With an extensive computational study we demonstrate that the resulting methods outperform all known methods for both the TD-MTDP and TD-DMP on instances taken from the literature
format Bài trích
author Duc, Minh Vua
Mike, Hewitt
Duc, D.Vuc
author_facet Duc, Minh Vua
Mike, Hewitt
Duc, D.Vuc
author_sort Duc, Minh Vua
title Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
title_short Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
title_full Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
title_fullStr Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
title_full_unstemmed Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
title_sort solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
publisher Elsevier
publishDate 2022
url https://www.sciencedirect.com/science/article/abs/pii/S0377221722000674?via%3Dihub
https://dlib.phenikaa-uni.edu.vn/handle/PNK/5737
https://doi.org/10.1016/j.ejor.2022.01.029
_version_ 1751856313862717440
score 8.891695

Similar Items