|
|
|
|
LEADER |
08770cam a22008172 4500 |
001 |
0-78371341X |
003 |
DE-627 |
005 |
20220717125548.0 |
007 |
cr uuu---uuuuu |
008 |
140424s2014 gw |||||om 00| ||ger c |
015 |
|
|
|a 14,O06
|2 dnb
|
016 |
7 |
|
|a 1050576969
|2 DE-101
|
024 |
7 |
|
|a urn:nbn:de:gbv:hil2-opus-2185
|2 urn
|
035 |
|
|
|a (DE-627)78371341X
|
035 |
|
|
|a (DE-576)9783713418
|
035 |
|
|
|a (DE-599)GBV78371341X
|
035 |
|
|
|a (OCoLC)881617611
|
035 |
|
|
|a (DE-101)1050576969
|
040 |
|
|
|a DE-627
|b ger
|c DE-627
|e rakwb
|
041 |
|
|
|a ger
|
044 |
|
|
|c XA-DE-NI
|
082 |
0 |
4 |
|a 004
|q DNB
|
082 |
0 |
4 |
|a 330
|
100 |
1 |
|
|a Nowak, Curt
|4 aut
|
245 |
1 |
0 |
|a Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister
|c Curt Nowak
|
246 |
1 |
|
|i abweichender Titel
|a Übers. des Hauptsacht.: Fast Optimal Path Search on Digital Road Maps -- Development, Implementation, and Example of Use at a Logistics Service Provider
|
264 |
|
1 |
|c 2014
|
300 |
|
|
|a Online-Ressource
|
336 |
|
|
|a Text
|b txt
|2 rdacontent
|
337 |
|
|
|a Computermedien
|b c
|2 rdamedia
|
338 |
|
|
|a Online-Ressource
|b cr
|2 rdacarrier
|
502 |
|
|
|a Hildesheim, Univ., Diss., 2014
|
520 |
|
|
|a Die Lösung vieler straßengebundener Transportplanungsprobleme aus der Praxis ist kombinatorisch aufwendig, komplex und manche der notwendigen Informationen liegen nicht hinreichend strukturiert vor. Standard-Lösungsverfahren sind daher für sie oft ungeeignet. Dies gilt auch für die operative Disposition bei Express- und Direkt-Kurierdienstleistern, bei der Entscheidungen über die Zuweisung von Fahrzeugen zu Aufträgen getroffen werden. Üblicherweise kommen für diese Aufgabe dialogorientierte Entscheidungsunterstützungssysteme (EUS) zum Einsatz, welche Vorschläge generieren, aus denen menschliche Disponenten unter Einbezug von domänenspezifischem Wissen den günstigsten auswählen. Lösungen, bei denen die Frachten mehrerer Aufträge auf einem Fahrzeug konsolidiert werden, sind dabei häufig besonders wirtschaftlich. Diese Arbeit beschäftigt sich mit der Optimierung der Disposition im Hinblick auf das Konsolidierungspotential der Frachten. Zum Aufdecken möglicher Ersparnisse durch Konsolidierung müssen viele alternative Fahrzeugrouten ermittelt und verglichen werden. Hierfür sind schnelle Verfahren zur Wegsuche von zentraler Bedeutung. Diese Verfahren bilden den ersten Schwerpunkt der Arbeit. Aufbauend auf einem vergleichenden Überblick "klassischer"' sowie aktueller Wegsucheverfahren wird mit den Contraction Hierarchies (CH) ein hierarchisches Verfahren in den Mittelpunkt gestellt, das ein besonders vorteilhaftes Verhältnis von Suchgeschwindigkeit zu benötigtem Speicherbedarf aufweist. Untersucht werden Optimierungen der Hierarchie-Erzeugung sowie neue Erweiterungen der Wegsuche in CH. In ausführlichen Benchmarks auf digitalen Straßenkarten des OpenStreetMap-Projekts werden die deutlichen Verbesserungen durch diese Erweiterungen empirisch nachgewiesen. Eine größere Realitätsnähe der berechneten Routen ergibt sich durch die Berücksichtigung von Abbiegebeschränkungen bei der Wegsuche. Nach der Vorstellung der in der Literatur hierfür üblichen Ansätze wird mit der adaptiven Wegsuche ein leistungsstarkes neues Verfahren für diesen Zweck präsentiert und für den Einsatz in CH angepasst. Die oben genannten Erweiterungen der Wegsuche sind mühelos auf dieses Verfahren übertragbar. Weitere Benchmarks unterstreichen die Vorteile der adaptiven gegenüber der in früherer Literatur eingesetzten pfeilbasierten Suche nach Wegen mit Abbiegebeschränkungen in CH. Für den zweiten Schwerpunkt der Arbeit, das Konsolidierungsproblem, wird zunächst ein ausführliches mathematisches Modell entwickelt. Es folgt eine Extraktion realitätsnaher Modellannahmen aus operativen Vergangenheitsdaten der IN tIME Express Logistik GmbH. Mit dem rekursiven Savingsverfahren wird schließlich eine neue Heuristik präsentiert, die es ermöglicht, Konsolidierungsvorschläge im Rahmen eines EUS zu generieren. Sie offenbart in mehreren, auf den Vergangenheitsdaten basierenden Benchmarks ein deutliches Kosteneinsparungspotential gegenüber früheren Dispositionsentscheidungen.
|
520 |
|
|
|a The solution to many real-world transportation planning problems is combinatorially comprehensive, complex, and some of the necessary information is not available in a sufficiently structured form. Hence, standard solving methods are often not applicable. This holds for courier and express providers' operational dispatching, where vehicles are assigned to customer orders. Typically, dialog-oriented decision support systems (DSS) are used to generate recommendations from which a human dispatcher selects the most profitable one by means of domain-specific knowledge. In this process, solutions that consolidate the freight of multiple customer orders onto a single vehicle are usually particularly favorable. This work examines optimization of the dispatching process with particular attention to the potential of freight consolidation. In order to uncover possible savings by consolidating, many alternative vehicle routes need to be determined and compared with each other. For this purpose, fast routing algorithms are essential. These algorithms form the first focus of this work. Based on a comparative literature overview of classical'' as well as current routing algorithms, the center of attention is put on contraction hierarchies (CH) as they provide a particularly favorable ratio of query speed-up to additional memory requirement. Both optimizations of hierarchy creation and new enhancements for queries in CH are studied. The considerable merits of these approaches are empirically shown through extensive benchmarks on digital road maps provided by the OpenStreetMap project. More realistic routes are obtained when routing algorithms take turn restrictions into account. First, common approaches from literature are presented for this purpose. Next, the adaptive search is introduced as a more efficient new approach, and adjusted for usage in CH. The above-mentioned query enhancements can easily be applied to this method. The advantages of the adaptive search in CH over the edge-based search that is employed for turn restriction aware routing in earlier literature is emphasized by further benchmarks. For the second focus of this work --~the vehicle routing problem with freight consolidation~-- first, a thorough mathematical model is developed. Next, model assumptions are extracted from past operational real-world data provided by IN tIME Express Logistik GmbH. Eventually, the recursive savings algorithm is introduced as a heuristic that can generate freight consolidation recommendations in the context of a DSS. Employed in multiple benchmarks based upon the past operational data, it reveals considerable cost savings compared to former dispatching decisions.
|
583 |
1 |
|
|z Langzeitarchivierung gewährleistet
|2 pdager
|
650 |
|
4 |
|a Wegsucheverfahren
|
650 |
|
4 |
|a Contraction Hierarchies
|
650 |
|
4 |
|a OpenStreetMap
|
650 |
|
4 |
|a Abbiegeverbote
|
650 |
|
4 |
|a Optimal Path Search
|
650 |
|
4 |
|a Contraction Hierarchies
|
650 |
|
4 |
|a OpenStreetMap
|
650 |
|
4 |
|a Turn Restrictions
|
655 |
|
7 |
|a Hochschulschrift
|0 (DE-588)4113937-9
|0 (DE-627)105825778
|0 (DE-576)209480580
|2 gnd-content
|
689 |
0 |
0 |
|D s
|0 (DE-588)4511937-5
|0 (DE-627)248012134
|0 (DE-576)213199033
|a Online-Ressource
|2 gnd
|
689 |
0 |
|
|5 (DE-627)
|
751 |
|
|
|a Hildesheim
|4 uvp
|
856 |
4 |
0 |
|u http://opus.bsz-bw.de/ubhi/volltexte/2014/218
|x Verlag
|z kostenfrei
|3 Volltext
|
856 |
4 |
0 |
|u http://nbn-resolving.de/urn:nbn:de:gbv:hil2-opus-2185
|q application/pdf
|x Resolving-System
|z kostenfrei
|3 Volltext
|
856 |
4 |
0 |
|u http://nbn-resolving.de/urn:nbn:de:gbv:hil2-opus-2185
|v 2014-06-18
|x Resolving-System
|3 Volltext
|
856 |
4 |
0 |
|u http://d-nb.info/1050576969/34
|v 2014-06-18
|x Langzeitarchivierung Nationalbibliothek
|3 Volltext
|
856 |
4 |
0 |
|u http://opus.bsz-bw.de/ubhi/volltexte/2014/218/
|v 2014-06-18
|x Verlag
|z kostenfrei
|3 Volltext
|
912 |
|
|
|a GBV-ODiss
|
935 |
|
|
|i Opus
|
951 |
|
|
|a BO
|
856 |
4 |
0 |
|u http://nbn-resolving.de/urn:nbn:de:gbv:hil2-opus-2185
|9 LFER
|
852 |
|
|
|a LFER
|z 2019-05-07T00:00:00Z
|
970 |
|
|
|c OD
|
971 |
|
|
|c EBOOK
|
972 |
|
|
|c EBOOK
|
973 |
|
|
|c EB
|
935 |
|
|
|a lfer
|
950 |
|
|
|a Netzpublikation
|
950 |
|
|
|a Online-Publikation
|
950 |
|
|
|a Computerdatei im Fernzugriff
|
950 |
|
|
|a Online-Dokument
|
950 |
|
|
|a On-line-Dokument
|
950 |
|
|
|a On-line-Publikation
|
950 |
|
|
|a Elektronische Publikation
|
950 |
|
|
|a Онлайн-ресурс
|
980 |
|
|
|a 78371341X
|b 0
|k 78371341X
|o 9783713418
|u 2023-04-28
|c lfer
|
SOLR
_version_ |
1764395678281236480 |
access_facet |
Electronic Resources |
author |
Nowak, Curt |
author_facet |
Nowak, Curt |
author_role |
aut |
author_sort |
Nowak, Curt |
author_variant |
c n cn |
callnumber-sort |
|
collection |
GBV-ODiss, lfer |
contents |
Die Lösung vieler straßengebundener Transportplanungsprobleme aus der Praxis ist kombinatorisch aufwendig, komplex und manche der notwendigen Informationen liegen nicht hinreichend strukturiert vor. Standard-Lösungsverfahren sind daher für sie oft ungeeignet. Dies gilt auch für die operative Disposition bei Express- und Direkt-Kurierdienstleistern, bei der Entscheidungen über die Zuweisung von Fahrzeugen zu Aufträgen getroffen werden. Üblicherweise kommen für diese Aufgabe dialogorientierte Entscheidungsunterstützungssysteme (EUS) zum Einsatz, welche Vorschläge generieren, aus denen menschliche Disponenten unter Einbezug von domänenspezifischem Wissen den günstigsten auswählen. Lösungen, bei denen die Frachten mehrerer Aufträge auf einem Fahrzeug konsolidiert werden, sind dabei häufig besonders wirtschaftlich. Diese Arbeit beschäftigt sich mit der Optimierung der Disposition im Hinblick auf das Konsolidierungspotential der Frachten. Zum Aufdecken möglicher Ersparnisse durch Konsolidierung müssen viele alternative Fahrzeugrouten ermittelt und verglichen werden. Hierfür sind schnelle Verfahren zur Wegsuche von zentraler Bedeutung. Diese Verfahren bilden den ersten Schwerpunkt der Arbeit. Aufbauend auf einem vergleichenden Überblick "klassischer"' sowie aktueller Wegsucheverfahren wird mit den Contraction Hierarchies (CH) ein hierarchisches Verfahren in den Mittelpunkt gestellt, das ein besonders vorteilhaftes Verhältnis von Suchgeschwindigkeit zu benötigtem Speicherbedarf aufweist. Untersucht werden Optimierungen der Hierarchie-Erzeugung sowie neue Erweiterungen der Wegsuche in CH. In ausführlichen Benchmarks auf digitalen Straßenkarten des OpenStreetMap-Projekts werden die deutlichen Verbesserungen durch diese Erweiterungen empirisch nachgewiesen. Eine größere Realitätsnähe der berechneten Routen ergibt sich durch die Berücksichtigung von Abbiegebeschränkungen bei der Wegsuche. Nach der Vorstellung der in der Literatur hierfür üblichen Ansätze wird mit der adaptiven Wegsuche ein leistungsstarkes neues Verfahren für diesen Zweck präsentiert und für den Einsatz in CH angepasst. Die oben genannten Erweiterungen der Wegsuche sind mühelos auf dieses Verfahren übertragbar. Weitere Benchmarks unterstreichen die Vorteile der adaptiven gegenüber der in früherer Literatur eingesetzten pfeilbasierten Suche nach Wegen mit Abbiegebeschränkungen in CH. Für den zweiten Schwerpunkt der Arbeit, das Konsolidierungsproblem, wird zunächst ein ausführliches mathematisches Modell entwickelt. Es folgt eine Extraktion realitätsnaher Modellannahmen aus operativen Vergangenheitsdaten der IN tIME Express Logistik GmbH. Mit dem rekursiven Savingsverfahren wird schließlich eine neue Heuristik präsentiert, die es ermöglicht, Konsolidierungsvorschläge im Rahmen eines EUS zu generieren. Sie offenbart in mehreren, auf den Vergangenheitsdaten basierenden Benchmarks ein deutliches Kosteneinsparungspotential gegenüber früheren Dispositionsentscheidungen., The solution to many real-world transportation planning problems is combinatorially comprehensive, complex, and some of the necessary information is not available in a sufficiently structured form. Hence, standard solving methods are often not applicable. This holds for courier and express providers' operational dispatching, where vehicles are assigned to customer orders. Typically, dialog-oriented decision support systems (DSS) are used to generate recommendations from which a human dispatcher selects the most profitable one by means of domain-specific knowledge. In this process, solutions that consolidate the freight of multiple customer orders onto a single vehicle are usually particularly favorable. This work examines optimization of the dispatching process with particular attention to the potential of freight consolidation. In order to uncover possible savings by consolidating, many alternative vehicle routes need to be determined and compared with each other. For this purpose, fast routing algorithms are essential. These algorithms form the first focus of this work. Based on a comparative literature overview of classical'' as well as current routing algorithms, the center of attention is put on contraction hierarchies (CH) as they provide a particularly favorable ratio of query speed-up to additional memory requirement. Both optimizations of hierarchy creation and new enhancements for queries in CH are studied. The considerable merits of these approaches are empirically shown through extensive benchmarks on digital road maps provided by the OpenStreetMap project. More realistic routes are obtained when routing algorithms take turn restrictions into account. First, common approaches from literature are presented for this purpose. Next, the adaptive search is introduced as a more efficient new approach, and adjusted for usage in CH. The above-mentioned query enhancements can easily be applied to this method. The advantages of the adaptive search in CH over the edge-based search that is employed for turn restriction aware routing in earlier literature is emphasized by further benchmarks. For the second focus of this work --~the vehicle routing problem with freight consolidation~-- first, a thorough mathematical model is developed. Next, model assumptions are extracted from past operational real-world data provided by IN tIME Express Logistik GmbH. Eventually, the recursive savings algorithm is introduced as a heuristic that can generate freight consolidation recommendations in the context of a DSS. Employed in multiple benchmarks based upon the past operational data, it reveals considerable cost savings compared to former dispatching decisions. |
ctrlnum |
(DE-627)78371341X, (DE-576)9783713418, (DE-599)GBV78371341X, (OCoLC)881617611, (DE-101)1050576969 |
dewey-full |
004, 330 |
dewey-hundreds |
000 - Computer science, information & general works, 300 - Social sciences |
dewey-ones |
004 - Data processing & computer science, 330 - Economics |
dewey-raw |
004, 330 |
dewey-search |
004, 330 |
dewey-sort |
14 |
dewey-tens |
000 - Computer science, knowledge & systems, 330 - Economics |
facet_912a |
GBV-ODiss |
facet_avail |
Online, Free |
facet_local_del330 |
Online-Ressource |
finc_class_facet |
Informatik, Soziologie, Wirtschaftswissenschaften |
fincclass_txtF_mv |
science-computerscience, economics |
format |
eBook, Thesis |
format_access_txtF_mv |
Thesis |
format_de105 |
Ebook |
format_de14 |
Book, E-Book |
format_de15 |
Book, E-Book |
format_del152 |
Buch |
format_detail_txtF_mv |
text-online-monograph-independent-thesis |
format_dezi4 |
e-Book |
format_finc |
Book, E-Book, Thesis |
format_legacy |
ElectronicBook |
format_legacy_nrw |
Book, E-Book |
format_nrw |
Book, E-Book |
format_strict_txtF_mv |
E-Thesis |
genre |
Hochschulschrift (DE-588)4113937-9 (DE-627)105825778 (DE-576)209480580 gnd-content |
genre_facet |
Hochschulschrift |
geogr_code |
not assigned |
geogr_code_person |
not assigned |
id |
0-78371341X |
illustrated |
Not Illustrated |
imprint |
2014 |
imprint_str_mv |
2014 |
institution |
DE-D117, DE-105, LFER, DE-Ch1, DE-15, DE-14, DE-Zwi2 |
is_hierarchy_id |
|
is_hierarchy_title |
|
isil_str_mv |
LFER |
kxp_id_str |
78371341X |
language |
German |
last_indexed |
2023-04-28T05:13:41.819Z |
local_heading_facet_dezwi2 |
Wegsucheverfahren, Contraction Hierarchies, OpenStreetMap, Abbiegeverbote, Optimal Path Search, Turn Restrictions, Online-Ressource |
marc024a_ct_mv |
urn:nbn:de:gbv:hil2-opus-2185 |
match_str |
nowak2014schnellewegsucheverfahrenaufdigitalenstrassenkartenentwicklungimplementierungundanwendungsbeispielbeieinemlogistikdienstleister |
mega_collection |
Verbunddaten SWB, Lizenzfreie Online-Ressourcen |
misc_de105 |
EBOOK |
oclc_num |
881617611 |
physical |
Online-Ressource |
publishDate |
2014 |
publishDateSort |
2014 |
publishPlace |
|
publisher |
|
record_format |
marcfinc |
record_id |
9783713418 |
recordtype |
marcfinc |
rvk_facet |
No subject assigned |
source_id |
0 |
spelling |
Nowak, Curt aut, Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister Curt Nowak, abweichender Titel Übers. des Hauptsacht.: Fast Optimal Path Search on Digital Road Maps -- Development, Implementation, and Example of Use at a Logistics Service Provider, 2014, Online-Ressource, Text txt rdacontent, Computermedien c rdamedia, Online-Ressource cr rdacarrier, Hildesheim, Univ., Diss., 2014, Die Lösung vieler straßengebundener Transportplanungsprobleme aus der Praxis ist kombinatorisch aufwendig, komplex und manche der notwendigen Informationen liegen nicht hinreichend strukturiert vor. Standard-Lösungsverfahren sind daher für sie oft ungeeignet. Dies gilt auch für die operative Disposition bei Express- und Direkt-Kurierdienstleistern, bei der Entscheidungen über die Zuweisung von Fahrzeugen zu Aufträgen getroffen werden. Üblicherweise kommen für diese Aufgabe dialogorientierte Entscheidungsunterstützungssysteme (EUS) zum Einsatz, welche Vorschläge generieren, aus denen menschliche Disponenten unter Einbezug von domänenspezifischem Wissen den günstigsten auswählen. Lösungen, bei denen die Frachten mehrerer Aufträge auf einem Fahrzeug konsolidiert werden, sind dabei häufig besonders wirtschaftlich. Diese Arbeit beschäftigt sich mit der Optimierung der Disposition im Hinblick auf das Konsolidierungspotential der Frachten. Zum Aufdecken möglicher Ersparnisse durch Konsolidierung müssen viele alternative Fahrzeugrouten ermittelt und verglichen werden. Hierfür sind schnelle Verfahren zur Wegsuche von zentraler Bedeutung. Diese Verfahren bilden den ersten Schwerpunkt der Arbeit. Aufbauend auf einem vergleichenden Überblick "klassischer"' sowie aktueller Wegsucheverfahren wird mit den Contraction Hierarchies (CH) ein hierarchisches Verfahren in den Mittelpunkt gestellt, das ein besonders vorteilhaftes Verhältnis von Suchgeschwindigkeit zu benötigtem Speicherbedarf aufweist. Untersucht werden Optimierungen der Hierarchie-Erzeugung sowie neue Erweiterungen der Wegsuche in CH. In ausführlichen Benchmarks auf digitalen Straßenkarten des OpenStreetMap-Projekts werden die deutlichen Verbesserungen durch diese Erweiterungen empirisch nachgewiesen. Eine größere Realitätsnähe der berechneten Routen ergibt sich durch die Berücksichtigung von Abbiegebeschränkungen bei der Wegsuche. Nach der Vorstellung der in der Literatur hierfür üblichen Ansätze wird mit der adaptiven Wegsuche ein leistungsstarkes neues Verfahren für diesen Zweck präsentiert und für den Einsatz in CH angepasst. Die oben genannten Erweiterungen der Wegsuche sind mühelos auf dieses Verfahren übertragbar. Weitere Benchmarks unterstreichen die Vorteile der adaptiven gegenüber der in früherer Literatur eingesetzten pfeilbasierten Suche nach Wegen mit Abbiegebeschränkungen in CH. Für den zweiten Schwerpunkt der Arbeit, das Konsolidierungsproblem, wird zunächst ein ausführliches mathematisches Modell entwickelt. Es folgt eine Extraktion realitätsnaher Modellannahmen aus operativen Vergangenheitsdaten der IN tIME Express Logistik GmbH. Mit dem rekursiven Savingsverfahren wird schließlich eine neue Heuristik präsentiert, die es ermöglicht, Konsolidierungsvorschläge im Rahmen eines EUS zu generieren. Sie offenbart in mehreren, auf den Vergangenheitsdaten basierenden Benchmarks ein deutliches Kosteneinsparungspotential gegenüber früheren Dispositionsentscheidungen., The solution to many real-world transportation planning problems is combinatorially comprehensive, complex, and some of the necessary information is not available in a sufficiently structured form. Hence, standard solving methods are often not applicable. This holds for courier and express providers' operational dispatching, where vehicles are assigned to customer orders. Typically, dialog-oriented decision support systems (DSS) are used to generate recommendations from which a human dispatcher selects the most profitable one by means of domain-specific knowledge. In this process, solutions that consolidate the freight of multiple customer orders onto a single vehicle are usually particularly favorable. This work examines optimization of the dispatching process with particular attention to the potential of freight consolidation. In order to uncover possible savings by consolidating, many alternative vehicle routes need to be determined and compared with each other. For this purpose, fast routing algorithms are essential. These algorithms form the first focus of this work. Based on a comparative literature overview of classical'' as well as current routing algorithms, the center of attention is put on contraction hierarchies (CH) as they provide a particularly favorable ratio of query speed-up to additional memory requirement. Both optimizations of hierarchy creation and new enhancements for queries in CH are studied. The considerable merits of these approaches are empirically shown through extensive benchmarks on digital road maps provided by the OpenStreetMap project. More realistic routes are obtained when routing algorithms take turn restrictions into account. First, common approaches from literature are presented for this purpose. Next, the adaptive search is introduced as a more efficient new approach, and adjusted for usage in CH. The above-mentioned query enhancements can easily be applied to this method. The advantages of the adaptive search in CH over the edge-based search that is employed for turn restriction aware routing in earlier literature is emphasized by further benchmarks. For the second focus of this work --~the vehicle routing problem with freight consolidation~-- first, a thorough mathematical model is developed. Next, model assumptions are extracted from past operational real-world data provided by IN tIME Express Logistik GmbH. Eventually, the recursive savings algorithm is introduced as a heuristic that can generate freight consolidation recommendations in the context of a DSS. Employed in multiple benchmarks based upon the past operational data, it reveals considerable cost savings compared to former dispatching decisions., Langzeitarchivierung gewährleistet pdager, Wegsucheverfahren, Contraction Hierarchies, OpenStreetMap, Abbiegeverbote, Optimal Path Search, Turn Restrictions, Hochschulschrift (DE-588)4113937-9 (DE-627)105825778 (DE-576)209480580 gnd-content, s (DE-588)4511937-5 (DE-627)248012134 (DE-576)213199033 Online-Ressource gnd, (DE-627), Hildesheim uvp, http://opus.bsz-bw.de/ubhi/volltexte/2014/218 Verlag kostenfrei Volltext, http://nbn-resolving.de/urn:nbn:de:gbv:hil2-opus-2185 application/pdf Resolving-System kostenfrei Volltext, http://nbn-resolving.de/urn:nbn:de:gbv:hil2-opus-2185 2014-06-18 Resolving-System Volltext, http://d-nb.info/1050576969/34 2014-06-18 Langzeitarchivierung Nationalbibliothek Volltext, http://opus.bsz-bw.de/ubhi/volltexte/2014/218/ 2014-06-18 Verlag kostenfrei Volltext, http://nbn-resolving.de/urn:nbn:de:gbv:hil2-opus-2185 LFER, LFER 2019-05-07T00:00:00Z |
spellingShingle |
Nowak, Curt, Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister, Die Lösung vieler straßengebundener Transportplanungsprobleme aus der Praxis ist kombinatorisch aufwendig, komplex und manche der notwendigen Informationen liegen nicht hinreichend strukturiert vor. Standard-Lösungsverfahren sind daher für sie oft ungeeignet. Dies gilt auch für die operative Disposition bei Express- und Direkt-Kurierdienstleistern, bei der Entscheidungen über die Zuweisung von Fahrzeugen zu Aufträgen getroffen werden. Üblicherweise kommen für diese Aufgabe dialogorientierte Entscheidungsunterstützungssysteme (EUS) zum Einsatz, welche Vorschläge generieren, aus denen menschliche Disponenten unter Einbezug von domänenspezifischem Wissen den günstigsten auswählen. Lösungen, bei denen die Frachten mehrerer Aufträge auf einem Fahrzeug konsolidiert werden, sind dabei häufig besonders wirtschaftlich. Diese Arbeit beschäftigt sich mit der Optimierung der Disposition im Hinblick auf das Konsolidierungspotential der Frachten. Zum Aufdecken möglicher Ersparnisse durch Konsolidierung müssen viele alternative Fahrzeugrouten ermittelt und verglichen werden. Hierfür sind schnelle Verfahren zur Wegsuche von zentraler Bedeutung. Diese Verfahren bilden den ersten Schwerpunkt der Arbeit. Aufbauend auf einem vergleichenden Überblick "klassischer"' sowie aktueller Wegsucheverfahren wird mit den Contraction Hierarchies (CH) ein hierarchisches Verfahren in den Mittelpunkt gestellt, das ein besonders vorteilhaftes Verhältnis von Suchgeschwindigkeit zu benötigtem Speicherbedarf aufweist. Untersucht werden Optimierungen der Hierarchie-Erzeugung sowie neue Erweiterungen der Wegsuche in CH. In ausführlichen Benchmarks auf digitalen Straßenkarten des OpenStreetMap-Projekts werden die deutlichen Verbesserungen durch diese Erweiterungen empirisch nachgewiesen. Eine größere Realitätsnähe der berechneten Routen ergibt sich durch die Berücksichtigung von Abbiegebeschränkungen bei der Wegsuche. Nach der Vorstellung der in der Literatur hierfür üblichen Ansätze wird mit der adaptiven Wegsuche ein leistungsstarkes neues Verfahren für diesen Zweck präsentiert und für den Einsatz in CH angepasst. Die oben genannten Erweiterungen der Wegsuche sind mühelos auf dieses Verfahren übertragbar. Weitere Benchmarks unterstreichen die Vorteile der adaptiven gegenüber der in früherer Literatur eingesetzten pfeilbasierten Suche nach Wegen mit Abbiegebeschränkungen in CH. Für den zweiten Schwerpunkt der Arbeit, das Konsolidierungsproblem, wird zunächst ein ausführliches mathematisches Modell entwickelt. Es folgt eine Extraktion realitätsnaher Modellannahmen aus operativen Vergangenheitsdaten der IN tIME Express Logistik GmbH. Mit dem rekursiven Savingsverfahren wird schließlich eine neue Heuristik präsentiert, die es ermöglicht, Konsolidierungsvorschläge im Rahmen eines EUS zu generieren. Sie offenbart in mehreren, auf den Vergangenheitsdaten basierenden Benchmarks ein deutliches Kosteneinsparungspotential gegenüber früheren Dispositionsentscheidungen., The solution to many real-world transportation planning problems is combinatorially comprehensive, complex, and some of the necessary information is not available in a sufficiently structured form. Hence, standard solving methods are often not applicable. This holds for courier and express providers' operational dispatching, where vehicles are assigned to customer orders. Typically, dialog-oriented decision support systems (DSS) are used to generate recommendations from which a human dispatcher selects the most profitable one by means of domain-specific knowledge. In this process, solutions that consolidate the freight of multiple customer orders onto a single vehicle are usually particularly favorable. This work examines optimization of the dispatching process with particular attention to the potential of freight consolidation. In order to uncover possible savings by consolidating, many alternative vehicle routes need to be determined and compared with each other. For this purpose, fast routing algorithms are essential. These algorithms form the first focus of this work. Based on a comparative literature overview of classical'' as well as current routing algorithms, the center of attention is put on contraction hierarchies (CH) as they provide a particularly favorable ratio of query speed-up to additional memory requirement. Both optimizations of hierarchy creation and new enhancements for queries in CH are studied. The considerable merits of these approaches are empirically shown through extensive benchmarks on digital road maps provided by the OpenStreetMap project. More realistic routes are obtained when routing algorithms take turn restrictions into account. First, common approaches from literature are presented for this purpose. Next, the adaptive search is introduced as a more efficient new approach, and adjusted for usage in CH. The above-mentioned query enhancements can easily be applied to this method. The advantages of the adaptive search in CH over the edge-based search that is employed for turn restriction aware routing in earlier literature is emphasized by further benchmarks. For the second focus of this work --~the vehicle routing problem with freight consolidation~-- first, a thorough mathematical model is developed. Next, model assumptions are extracted from past operational real-world data provided by IN tIME Express Logistik GmbH. Eventually, the recursive savings algorithm is introduced as a heuristic that can generate freight consolidation recommendations in the context of a DSS. Employed in multiple benchmarks based upon the past operational data, it reveals considerable cost savings compared to former dispatching decisions., Wegsucheverfahren, Contraction Hierarchies, OpenStreetMap, Abbiegeverbote, Optimal Path Search, Turn Restrictions, Hochschulschrift, Online-Ressource |
swb_id_str |
9783713418 |
title |
Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister |
title_alt |
Übers. des Hauptsacht.: Fast Optimal Path Search on Digital Road Maps -- Development, Implementation, and Example of Use at a Logistics Service Provider |
title_auth |
Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister |
title_full |
Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister Curt Nowak |
title_fullStr |
Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister Curt Nowak |
title_full_unstemmed |
Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister Curt Nowak |
title_short |
Schnelle Wegsucheverfahren auf digitalen Straßenkarten -- Entwicklung, Implementierung und Anwendungsbeispiel bei einem Logistikdienstleister |
title_sort |
schnelle wegsucheverfahren auf digitalen straßenkarten entwicklung implementierung und anwendungsbeispiel bei einem logistikdienstleister |
topic |
Wegsucheverfahren, Contraction Hierarchies, OpenStreetMap, Abbiegeverbote, Optimal Path Search, Turn Restrictions, Hochschulschrift, Online-Ressource |
topic_facet |
Wegsucheverfahren, Contraction Hierarchies, OpenStreetMap, Abbiegeverbote, Optimal Path Search, Turn Restrictions, Hochschulschrift, Online-Ressource |
url |
http://opus.bsz-bw.de/ubhi/volltexte/2014/218, http://nbn-resolving.de/urn:nbn:de:gbv:hil2-opus-2185, http://d-nb.info/1050576969/34, http://opus.bsz-bw.de/ubhi/volltexte/2014/218/ |
urn |
urn:nbn:de:gbv:hil2-opus-2185 |