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, Vu, Mike, Hewitt, Duc D.Vuc
Format: Bài trích
Language:English
Published: Elsevier 2022
Subjects:
Tour Duration Problem
Dynamic Discretization Discovery
Online Access:https://www.sciencedirect.com/science/article/abs/pii/S0377221722000674?via%3Dihub
https://dlib.phenikaa-uni.edu.vn/handle/PNK/5877
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-5877
record_format dspace
spelling oai:localhost:PNK-58772022-08-17T05:54:54Z Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery Duc Minh, Vu Mike, Hewitt Duc D.Vuc Tour Duration Problem 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 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-07-13T01:59:47Z 2022-07-13T01:59:47Z 2022 Bài trích https://www.sciencedirect.com/science/article/abs/pii/S0377221722000674?via%3Dihub https://dlib.phenikaa-uni.edu.vn/handle/PNK/5877 https://doi.org/10.1016/j.ejor.2022.01.029 en Elsevier
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic Tour Duration Problem
Dynamic Discretization Discovery
spellingShingle Tour Duration Problem
Dynamic Discretization Discovery
Duc Minh, Vu
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, Vu
Mike, Hewitt
Duc D.Vuc
author_facet Duc Minh, Vu
Mike, Hewitt
Duc D.Vuc
author_sort Duc Minh, Vu
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/5877
https://doi.org/10.1016/j.ejor.2022.01.029
_version_ 1751856285670703104
score 8.889492

Similar Items