کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
384682 660853 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A Simulated Annealing-based parallel multi-objective approach to vehicle routing problems with time windows
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
A Simulated Annealing-based parallel multi-objective approach to vehicle routing problems with time windows
چکیده انگلیسی

The Capacitated Vehicle Routing Problem with Time Windows (VRPTW) consists in determining the routes of a given number of vehicles with identical capacity stationed at a central depot which are used to supply the demands of a set of customers within certain time windows. This is a complex multi-constrained problem with industrial, economic, and environmental implications that has been widely analyzed in the past. This paper deals with a multi-objective variant of the VRPTW that simultaneously minimizes the travelled distance and the imbalance of the routes. This imbalance is analyzed from two perspectives: the imbalance in the distances travelled by the vehicles, and the imbalance in the loads delivered by them. A multi-objective procedure based on Simulated Annealing, the Multiple Temperature Pareto Simulated Annealing (MT-PSA), is proposed in this paper to cope with these multi-objective formulations of the VRPTW. The procedure MT-PSA and an island-based parallel version of MT-PSA have been evaluated and compared with, respectively, sequential and island-based parallel implementations of SPEA2. Computational results obtained on Solomon’s benchmark problems show that the island-based parallelization produces Pareto-fronts of higher quality that those obtained by the sequential versions without increasing the computational cost, while also producing significant reduction in the runtimes while maintaining solution quality. More specifically, for the most part, our procedure MT-PSA outperforms SPEA2 in the benchmarks here considered, with respect to the solution quality and execution time.


► It is presented the Multiple-Temperature Pareto Simulated Annealing (MT-PSA).
► The sequential MT-PSA is parallelized with MPI using the island-based model.
► The algorithms are evaluated in a vehicle routing problem with time-windows.
► The island-based parallelization using MPI outperforms to the sequential algorithm.
► Parallel implementations obtain good results in comparison with the best known solutions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Expert Systems with Applications - Volume 40, Issue 5, April 2013, Pages 1696–1707
نویسندگان
, , , , ,