Vehicle flow formulation for two-echelon time-constrained vehicle routing problem
Two-echelon routing problems, including variants such as the two-echelon vehicle routing problem (2E-VRP) and the two-echelon location routing problem (2E-LRP), involve assignment and location decisions. However, the two-echelon time-constrained vehicle routing problem (2E-TVRP) that caters to from-...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
KeAi Communications Co., Ltd.
2019-06-01
|
| Series: | Journal of Management Science and Engineering |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2096232019300770 |
| _version_ | 1828848854572728320 |
|---|---|
| author | Hongqi Li Ming Bai Yibin Zhao Changzhi Dai |
| author_facet | Hongqi Li Ming Bai Yibin Zhao Changzhi Dai |
| author_sort | Hongqi Li |
| collection | DOAJ |
| description | Two-echelon routing problems, including variants such as the two-echelon vehicle routing problem (2E-VRP) and the two-echelon location routing problem (2E-LRP), involve assignment and location decisions. However, the two-echelon time-constrained vehicle routing problem (2E-TVRP) that caters to from-linehaul-to-delivery practices does not involve assignment decisions. This routing problem variant for networks with two echelons has not yet attracted enough research interest. Localized or long-distance services suffer from the lack of the assignment decisions between satellites and customers. Therefore, the 2E-TVRP, rather than using assignment decisions, adopts time constraints to decide the routes on each of the two interacting echelons: large-capacity vehicles transport cargoes among satellites on the first echelon, and small-capacity vehicles deliver cargoes from satellites to customers on the second echelon. This study introduces a mixed integer linear programming model for the 2E-TVRP and proposes a heuristic algorithm that incorporates the savings algorithm followed by a variable neighborhood search phase. Illustrative examples are used to test the mathematical formulation and the heuristic and a case study is used to demonstrate that the heuristic can effectively solve realistic-size instances of the 2E-TVRP. Keywords: Vehicle routing, Two-echelon, Time constraints, Mixed integer linear programming, Variable neighborhood search |
| first_indexed | 2024-12-12T22:38:46Z |
| format | Article |
| id | doaj.art-75089a2b95164937b38238a1b79ea589 |
| institution | Directory Open Access Journal |
| issn | 2096-2320 |
| language | English |
| last_indexed | 2024-12-12T22:38:46Z |
| publishDate | 2019-06-01 |
| publisher | KeAi Communications Co., Ltd. |
| record_format | Article |
| series | Journal of Management Science and Engineering |
| spelling | doaj.art-75089a2b95164937b38238a1b79ea5892022-12-22T00:09:23ZengKeAi Communications Co., Ltd.Journal of Management Science and Engineering2096-23202019-06-01427590Vehicle flow formulation for two-echelon time-constrained vehicle routing problemHongqi Li0Ming Bai1Yibin Zhao2Changzhi Dai3Corresponding author. School of Transportation Science and Engineering, Beihang University, No. 37 Xueyuan Road, Haidian District, Beijing, 100191, China.; School of Transportation Science and Engineering, Beihang University, Beijing, 100191, ChinaSchool of Transportation Science and Engineering, Beihang University, Beijing, 100191, ChinaSchool of Transportation Science and Engineering, Beihang University, Beijing, 100191, ChinaSchool of Transportation Science and Engineering, Beihang University, Beijing, 100191, ChinaTwo-echelon routing problems, including variants such as the two-echelon vehicle routing problem (2E-VRP) and the two-echelon location routing problem (2E-LRP), involve assignment and location decisions. However, the two-echelon time-constrained vehicle routing problem (2E-TVRP) that caters to from-linehaul-to-delivery practices does not involve assignment decisions. This routing problem variant for networks with two echelons has not yet attracted enough research interest. Localized or long-distance services suffer from the lack of the assignment decisions between satellites and customers. Therefore, the 2E-TVRP, rather than using assignment decisions, adopts time constraints to decide the routes on each of the two interacting echelons: large-capacity vehicles transport cargoes among satellites on the first echelon, and small-capacity vehicles deliver cargoes from satellites to customers on the second echelon. This study introduces a mixed integer linear programming model for the 2E-TVRP and proposes a heuristic algorithm that incorporates the savings algorithm followed by a variable neighborhood search phase. Illustrative examples are used to test the mathematical formulation and the heuristic and a case study is used to demonstrate that the heuristic can effectively solve realistic-size instances of the 2E-TVRP. Keywords: Vehicle routing, Two-echelon, Time constraints, Mixed integer linear programming, Variable neighborhood searchhttp://www.sciencedirect.com/science/article/pii/S2096232019300770 |
| spellingShingle | Hongqi Li Ming Bai Yibin Zhao Changzhi Dai Vehicle flow formulation for two-echelon time-constrained vehicle routing problem Journal of Management Science and Engineering |
| title | Vehicle flow formulation for two-echelon time-constrained vehicle routing problem |
| title_full | Vehicle flow formulation for two-echelon time-constrained vehicle routing problem |
| title_fullStr | Vehicle flow formulation for two-echelon time-constrained vehicle routing problem |
| title_full_unstemmed | Vehicle flow formulation for two-echelon time-constrained vehicle routing problem |
| title_short | Vehicle flow formulation for two-echelon time-constrained vehicle routing problem |
| title_sort | vehicle flow formulation for two echelon time constrained vehicle routing problem |
| url | http://www.sciencedirect.com/science/article/pii/S2096232019300770 |
| work_keys_str_mv | AT hongqili vehicleflowformulationfortwoechelontimeconstrainedvehicleroutingproblem AT mingbai vehicleflowformulationfortwoechelontimeconstrainedvehicleroutingproblem AT yibinzhao vehicleflowformulationfortwoechelontimeconstrainedvehicleroutingproblem AT changzhidai vehicleflowformulationfortwoechelontimeconstrainedvehicleroutingproblem |