- مبلغ: ۸۶,۰۰۰ تومان
- مبلغ: ۹۱,۰۰۰ تومان
The paper presents an effective algorithm for solving Vehicle Routing Problem with Dynamic Requests based on memetic algorithms. The proposed method is applied to a widely-used set of 21 benchmark problems yielding 14 new best-know results when using the same numbers of fitness function evaluations as the comparative methods. Apart from encouraging numerical outcomes, the main contribution of the paper is investigation into the importance of the so-called starting delay parameter, whose appropriate selection has a crucial impact on the quality of results. Another key factor in accomplishing high quality results is attributed to the proposed effective mechanism of knowledge transfer between partial solutions developed in consecutive time slices. While particular problem encoding and memetic local optimization scheme were already presented in the literature, the novelty of this work lies in their innovative combination into one synergetic system as well as their application to a different problem than in the original works.
7. Summary and conclusions
This paper presents a memetic approach to solving the Vehicle Routing Problem with Dynamic Requests. The algorithm was tested on a well-established set of benchmarks and proved to be an effective and reliable method, capable of finding 14 new best results out of 21 tested problems, using the same numbers of fitness function evaluations. It is worth underlying that, except for some parameter tuning, the method was not optimized for solving this particular set of benchmarks. Furthermore, the proposed algorithm can, in principle, be applied to solving other VRPDR benchmarks with no specific adjustments as the selected parameters seem to be universally useful (though certainly not optimal in strict sense). Our algorithm relies on problem encoding previously introduced in  and adopts memetic optimization scheme proposed in , however, both these factors are combined in a novel manner as parts of the newly-designed system and applied to the problem other that those considered in the source papers. Furthermore, while memetic optimization is definitely an important part of the overall solution method, the paramount feature is the starting delay parameter which heuristically administers the dispatching times of the vehicles.