Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: CVRP

Sortuj według:

Ogranicz wyniki do:

Accelerating the Clarke-Wright algorithm using GPUs

Guerriero Francesca, Saccomanno Francesco Paolo

Control and Cybernetics

2024

Vol. 53, No. 2

371--383

The Capacitated Vehicle Routing Problem (CVRP) is a combinatorial optimization problem that seeks to determine the optimal set of routes for a fleet of vehicles, with limited capacity, to deliver goods to customers while minimizing the total cost. Due to its NP-hard nature, finding exact solutions for the large-scale CVRP instances is computationally intractable. Therefore, heuristics and metaheuristics are widely employed to find approximate optimal solutions. Among these, the Clarke-Wright (CW) algorithm is a popular greedy approach that constructs routes by iteratively merging nodes to minimize transportation costs. This study presents an implementation of the CW algorithm in graphics processing units (GPUs) using the CUDA (Compute Unified Device Architecture) framework. The GPU implementation is compared to its CPU counterpart in terms of execution time and performance. The results demonstrate significant speed-ups achieved by the GPU implementation, particularly for large-scale instances. Performance gains can be attributed to the parallel processing capabilities of GPUs, enabling efficient execution of the algorithm computational steps.

Capacitated vehicle routing problem with CO2 rates for urban transport

Lewczuk K., Żak J., Pyza D., Jacyna-Gołda I.

Prace Naukowe Politechniki Warszawskiej. Transport

2013

z. 97

337--348

Paper discusses problem of routing freight vehicles in urban areas according to criteria of CO2 emission and traveling time. Time-dependant traffic conditions for urban areas are defined. Ecological aspects of carbon dioxide emission in urban conditions are a base of mathematical model of time-dependent capacitated vehicle routing problem with CO2 emission level as a criteria function. Model comprises characteristics of urban transport infrastructure, time-dependent traffic density, and different types of vehicles according to the task requirements. Model is implemented onto representation of real transport network and solved for given data with two step-heuristics basing on modified A-star algorithm and genetic programming. Appropriate results, future research directions and other potential uses are presented and discussed.

W artykule podjęto zagadnienie trasowania pojazdów dostawczych w warunkach miejskich ze względu na emisję CO2 i czas przejazdu. Warunki ruchowe charakterystyczne dla obszarów miejskich i ich zależność od czasu zostały zdefiniowane. Kwestie ekologiczne emisji CO2 w warunkach miejskich zostały wykorzystane do skonstruowania modelu matematycznego dla zależnego od czasu problemu trasowania pojazdów z określoną masą ładunkową, którego funkcja kryterium zakłada minimalizację emisji dwutlenku węgla. W modelu ujęto charakterystyki infrastruktury transportowej obszarów zurbanizowanych, natężenie ruchu zależne od pory dnia i różne typy pojazdów dobierane w zależności od wielkości realizowanego zadania. Model został zaimplementowany w rzeczywistej sieci transportowej. Dla danych projektowych wykonano obliczenia z wykorzystaniem dwustopniowej heurystyki bazującej na zmodyfikowanym algorytmie A* oraz programowaniu genetycznym. Otrzymane rezultaty, kierunki przyszłych badań oraz potencjalne zastosowania zostały zaprezentowane i omówione.