Single Vehicle Routing in Reconfigurable Manufacturing Environments Using the Bump-Surface Concept
This paper presents a new approach for solving a generalization of the vehicle routing with pickup and delivery problem (VRPDP) for an automatic guided vehicle (AGV) moving in a 2D rapidly changing shop floor environment. Rabid changes are assumed to occur in the facilities layout of the shop floor, such as in the shape, size and location of (the obstacles) corridors, walls, machines, furniture, etc., as well as, changes in the positions of the pickup and delivery (P/D) stations. The problem to be faced is thereby a dual NP-hard combinatorial problem combining the characteristics and constraints of a motion planning problem (MPP) and VRPDP. The objective is to determine the optimum (minimum length) collision-free vehicle tour through all the P/D stations passing from each one of them exactly once. The proposed approach consists of two main phases: first, the Bump-Surface concept is used to represent the 2D manufacturing environment by a 2D B-Spline surface embedded in 3D Euclidean space. Then, the generated surface is being searched for an optimum vehicle route (satisfying the above mentioned constraints) using a genetic algorithm. The performance of the proposed approach is investigated and discussed through simulated experiments.
| Attachment | Size |
|---|---|
| iproms_2007.wmv | 1.07 MB |
Dear authors,
I found very interesting this paper, especially, how the problem was defined/developed so it could be solved by a GA. I have a question regarding the genetic operator used in this work. I understand that the first part of the chromosome is basically a TSP so if a standard crossover operator is used (like a single point crossover) this may produce an invalid individual, so this is why the OX operator is used. My question is why was the order crossover (OX) chosen instead of the other TSP type crossover operators, like the cyclic crossover (CX), partially mapped crossover (PMX), etc…? Did you conduct any experiments which helped you conclude that this was the most appropriate operator for this particular problem?
Thank you,
Gonzalo