A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs
| Autor: | Franziska Theurich, Guntram Scheithauer, Andreas Fischer |
|---|---|
| Přispěvatelé: | Publica |
| Rok vydání: | 2021 |
| Předmět: |
T57-57.97
Mathematical optimization Applied mathematics. Quantitative methods Control and Optimization railway infrastructure maintenance scheduling Branch and bound Computer science Railway maintenance scheduling QA75.5-76.95 Management Science and Operations Research Solver Track (rail transport) Partition (database) customer costs Scheduling (computing) Reduction (complexity) Computational Mathematics Permutation Electronic computers. Computer science Modeling and Simulation Vehicle routing problem vehicle routing problem branch-and-bound |
| Zdroj: | EURO Journal on Computational Optimization, Vol 9, Iss, Pp 100003-(2021) |
| ISSN: | 2192-4406 |
| DOI: | 10.1016/j.ejco.2020.100003 |
| Popis: | An important aspect in railway maintenance management is the scheduling of tamping actions in which two aspects need to be considered: first, the reduction of travel costs for crews and machinery; and second, the reduction of time-dependent costs caused by bad track condition. We model the corresponding planning problem as a Vehicle Routing Problem with additional customer costs. Due to the particular objective function, this kind of Vehicle Routing Problem is harder to solve with conventional methods. Therefore, we develop a branch-and-bound approach based on a partition and permutation model. We present two branching strategies, the first appends one job at the end of a route in each branching step and the second includes one job inside a route in each branching step; and analyze their pros and cons. Furthermore, different lower bounds for the customer costs and the travel costs are defined and compared. The performance of the branch-and-bound method is analyzed and compared with a commercial solver. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|