| Author | Siwaporn Kunnapapdeelert |
| Note | A dissertation submitted in partial fulfillment of the requirements for the
degree of Doctor of Engineering in
Industrial and Manufacturing Engineering |
| Publisher | Asian Institute of Technology |
| Abstract | The main purpose of this dissertation is to develop enhanced Differential Evolution (DE) algorithms for solving multi-depot vehicle routing problem with multiple pickup and delivery requests (GVRP-MDMPDR). The first enhanced algorithm is DE with subgrouping of vectors in the mutation process (SGMDE). It is done by dividing the DE vectors into two subgroups with each subgroup applies different mutation process. The two mutation approaches that produce new vectors are based on the experience from randomly selected vectors and global best vectors. The information sharing across the other groups is accomplished by allowing vectors from all groups to be selected in the mutation process. The second enhanced algorithm, DE algorithm with subgrouping of vectors in the crossover process (SGCDE). The vectors are also classified into two groups. One group applies exponential crossover and the other uses binomial crossover. The information sharing across the other groups is accomplished in the same way by allowing vectors from all groups to be selected in the mutation process. The third proposed algorithm is called switching mutation differential evolution (SWMDE) with two different mutation strategies (DE/best/1/exp and DE/localbest/1/exp) that are used alternately to enhance the DE algorithm. One mutation scheme is used at the start of the algorithm and the algorithm will switch to the other mutation scheme whenever the solutions did not improve after a fixed number of iterations. The fourth proposed algorithm is switching crossover differential evolution (SWCDE) which utilizes two different crossover methods (exponential crossover and binomial crossover) interchangeably. This enhancement starts with one crossover process and allows switching to the other crossover process whenever the solution quality is unimproved for some predefined number of consecutive iterations. All of DE-based algorithms are implemented SD1, SD2, and SD3. Their performances are tested and compared. The results show that SD1 provides the better results than those of SD2 and SD3 but the computational times required are at least ten times longer than those of SD2 and SD3. Moreover, the combination of solution representations SD1 and SD3 with DE-based algorithms can find new best known solutions in 25 out of 30 test problem instances. This implies that the new proposed algorithms based on solution representation SD3 are more attractive for solving GVRP-MDMPDR so they are recommended to replace the DE based on SD1. Performance of all enhanced algorithms are compared based on the statistical pairwise tests, they show that SGCDE provides mostly the better solution that those of SGMDE, SWCDE, SWMDE and classical DE algorithm, respectively. Whereas, SWMDE provides the better results than those of classical DE in only some test cases. Further, it found that the enhancement of DE algorithm in crossover process for both subgrouping and switching schemes are more effective than the enhancement in mutation process. |
| Year | 2017 |
| Type | Dissertation |
| School | School of Engineering and Technology (SET) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Microelectronics (ME) |
| Chairperson(s) | Voratas Kachitvichyanukul ; |
| Examination Committee(s) | Huynh Trung Luong;Do Ba Khang;Wu, Muh-Cherng ; |
| Scholarship Donor(s) | Royal Thai Government; |
| Degree | Thesis (Ph.D.) -- Asian Institute of Technology, 2017 |