Publikation: Efficient and Easy-to-Implement Mixed-I...
Stammdaten
Titel: | Efficient and Easy-to-Implement Mixed-Integer Linear Programs for the Traveling Salesperson Problem with Time Windows |
Untertitel: | |
Kurzfassung: | The NP-hard Traveling Salesperson Problem with Time Windows (TSPTW) is concerned with visiting a given set of customers within their assigned time windows such that a given objective function is minimized. In contrast to traditional problems, where each customer gets assigned its own time window, in modern web-based systems the supplying company defines a set of time windows, from which the customer can then choose one of them. Therefore, by design, typically several customers are assigned to the same time window. Motivated by this development and the fact that practitioners seek for formulations that can easily and quickly be implemented, we introduce two mixed-integer linear programs (MILPs) for the asymmetric TSPTW that allow to computationally exploit the structure of the time windows and are also applicable for asymmetric travel times, for which the triangle inequalities do not hold. In particular we analyze and exploit the relations between time windows in order to reduce the number of binary variables in our MILPs. For the special case of non-overlapping time windows we can further simplify the constraint set and also reduce the number of continuous variables needed. Finally, we demonstrate the efficiency of our MILPs on benchmark instances related to an online shopping application. |
Schlagworte: |
Publikationstyp: | Beitrag in Proceedings (Autorenschaft) |
Erscheinungsdatum: | 01.05.2017 (Online) |
Erschienen in: |
Transportation Research Procedia
Transportation Research Procedia
(
Elsevier;
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | 30 |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 157 - 166 |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 01.05.2017 |
ISBN (e-book): | - |
eISSN: | - |
DOI: | http://dx.doi.org/10.1016/j.trpro.2018.09.018 |
Homepage: | https://doi.org/10.1016/j.trpro.2018.09.018 |
Open Access |
|
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen |
|
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte: |
|
Publikationen: | Keine verknüpften Publikationen vorhanden |
Veranstaltungen: | Keine verknüpften Veranstaltung vorhanden |
Vorträge: |
|