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...
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Định dạng: | Bài trích |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
Elsevier
2022
|
| Chủ đề: | |
| Truy cập trực tuyến: | 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 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| 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.887836 |