Multi-objective Discrete Quantum PSO for dynamic environments

Abstract

Dynamiske miljøer og flere objektiver er gjentagende problemer i den virkelige verden. Det er ikke gjort grundig forskning på en kombinasjon av disse problemene. I oppgaven blir det lagt frem en modell som kombinerer den dynamiske algoritmen mQSO og algoritmen MODPSO som operer på diskrete og flere objektiv problemer. Det blir også foreslått og evaluert ulike diskrete representasjoner. Modellen er utviklet for å løse Vehicle Routing Problem (VRP) og er testet på Solomon datasettet og et datasett fra den norske hjemmesykepleien. Modellen forsøker å løse dynamiske VRP'er hvor endringer slik som at nye kunder eller behov kan dukke opp. De dynamiske egenskapene lar modellen overføre kunnskap fra før en endring skjer til etter som kan være med på å redusere nødvendig prosesseringstid. Den foreslåtte modellen er i stand til å håndtere disse dynamiske endringer og samtidig optimalisere flere objektiver og ta hensyn til begrensninger slik som tidsvinduer.

Dynamic environments and multiple objectives are prominent in real-world problems. However, a combination of dynamic environments and multi-objectives is not extensively studied. In the thesis a model is proposed that combines the dynamic handling algorithm mQSO and the algorithm MODPSO which operates on discrete multi-objective problems. Further, different types of discrete representations are proposed and evaluated. The model is developed to solve the Vehicle Routing Problem (VRP) and is tested on the Solomon data set and a data set from the Norwegian home care. The model attempts to solve dynamic VRPs where changes to the environment like the appearance of new customers or demands can occur. The dynamic abilities makes the model able to transfer knowledge from before to after a change which can reduce computational cost. The proposed model is able to handle these changes while optimizing multiple objectives and handling constraints such as time windows.