Tham khảo tài liệu 'contemporary robotics - challenges and solutions part 10', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Cooperation Control in Distributed Population-based Algorithms using a Multi-agent Approach Application to a real-life Vehicle Routing Problem 261 VS 0 S c 2 . n Vk e I us ys xijk lijk vc bc e 0 1 Si jeSxijk - n2yS Is _ 1 SieS sjeSxijk uS 1 u ys 1 1 7 8 The goal 1 is to determine a set of closed walks vehicle trips of minimum total cost. Constraint 2 ensures that a vehicle coming into a node must leave it again. Constraint 3 ensures that a required edge is also traversed. Each required edge is serviced by one single trip 4 such that each trip starts and ends at the depot and the total demand handled by any vehicle does not exceed W 5 . A container must be collected if its filling rate is more than 20 or it is a black spot 6 . Finally illegal sub-trips are forbidden by constraint 8 which requires additional binary variables such as yk and u . Since the CARP is NP-hard large scale instances must be solved in practice using heuristics. Among fast constructive methods one can cite Path-Scanning Golden et al. 1983 Augment-Merge Golden Wong 1981 and Ulusoy s splitting technique Ulusoy 1985 . Available metaheuristics are very recent and include tabu search methods Hertz et al. 2000 Belenguer Benavent 2003 guided local search Beullens et al. 2003 and memetic algorithms Lacomme et al. 2001 Lacomme et al. 2004 . All these heuristics algorithms can be evaluated through lower bounds Amberg Vofi 2002 . 6. MAF-DISTA implementation for UWCOP We conducted two series of experiments to compare the corresponding performance for evolutionary computation with and without parallelism. In these experiments each mobile agent executes a conventional genetic algorithm. The genetic algorithm GA developed in this work uses several components of the genetic algorithm and the effective memetic algorithm proposed by Lacomme et al. 2001 Lacomme et al. 2004 for the CARP. The common parts are described below Solution encoding The network is coded as a symmetric digraph in which each edge is .
