Publication detail

Modification of the Clarke and Wright Algorithm with a Dynamic Savings Matrix

Authors: Fikejz Jan | Brázdová Markéta | Jánošíková Ludmila

Year: 2024

Type of publication: článek v odborném periodiku

Name of source: Journal of Advanced Transportation

Page from-to: 29 March 2024

Titles:

Language	Name	Abstract	Keywords
cze	Modifikace Clarkeho a Wrightova algoritmu s maticí dynamických úspor	Proces vyzvednutí a dodání zboží se často týká distribučních logistických problémů. Úkolem je dodávat zboží ze skladů zákazníkům za specifických okolností. Snahy o optimalizaci procesu jsou z velké části zaměřeny na snížení celkových nákladů na přepravu zboží. Mezi prominentní algoritmy pro řešení základního typu problému dodávky (či vyzvednutí), který zahrnuje jediné depo a homogenní vozový park, patří algoritmus vyvinutý Clarkem a Wrightem v roce 1964. Tento algoritmus minimalizuje přepravní náklady maximalizací dosažených úspor. spojením více cest do jedné. Tento dokument se primárně zaměřuje na řešení problému vyzvednutí a doručení, kdy musí být zboží doručeno a prázdné obaly shromážděny v jediném procesu. Požadavek zákazníka může být směrován z depa nebo od jiného zákazníka. Obdobně může být cílem požadavku depo nebo jiný zákazník. Na rozdíl od původní verze Clarkeho a Wrightova algoritmu jsou počáteční trasy vytvořeny pro uspokojení dodacích objednávek, a proto se stejný zákazník může vyskytovat na více trasách. V důsledku toho může nastat situace, kdy musí být během výpočtu kombinovány dvě trasy obsahující jeden nebo více společných vrcholů. Navíc tyto vrcholy nemusí být nejvzdálenějšími vrcholy tras. Tuto situaci nelze řešit použitím původní verze Clarkeho a Wrightova algoritmu, a proto navrhujeme jeho úpravu. Sloučení tras přes vnitřní vrcholy znamená, že úspory nákladů závisí na konfiguracích tras, a proto je nelze vypočítat a priori. Místo toho je třeba použít dynamickou matici úspor.	Modifikace; Clarkeho; Wrightova; algoritmu; maticí; dynamických; úspor
eng	Modification of the Clarke and Wright Algorithm with a Dynamic Savings Matrix	The goods collection and delivery process often relates to distribution logistics problems. The task is to deliver goods from warehouses to customers under specific circumstances. Efforts to optimize the process are largely aimed at reducing overall costs of goods transportation. Among the prominent algorithms for solving the basic type of the delivery (or collection) problem, which includes a single depot and a homogeneous vehicle fleet, is the algorithm developed by Clarke and Wright in 1964. This algorithm minimizes transportation costs by maximizing the savings achieved through merging multiple routes into one. This paper primarily aims to solve the pickup and delivery problem where the goods must be delivered and empty packaging collected in a single process. The request of a customer can be routed from the depot or from another customer. Similarly, the destination of the request may be the depot or another customer. Unlike the original version of the Clarke and Wright algorithm, the initial routes are created to satisfy delivery orders, and therefore, the same customer can occur in multiple routes. Consequently, a situation may arise in which two routes containing one or more common vertices must be combined during the calculation. Furthermore, these vertices need not be the outermost vertices of the routes. This situation cannot be addressed by using the original version of the Clarke and Wright algorithm, and that is why we propose its modification. Merging routes through inner vertices means that the cost savings depend on the configurations of the routes, and therefore, they cannot be calculated a priori. Instead, the dynamic savings matrix must be used.	Modification; the; Clarke; and; Wright; Algorithm; with; Dynamic; Savings; Matrix

Search

Login for students

Login for employees

Publication detail

Department

Map

Services

Popular Links