Improved Squeaky Wheel Optimisation for Driver Scheduling
This paper presents a technique called Improved Squeaky Wheel Optimisation (ISWO) for driver scheduling problems. It improves the original Squeaky Wheel Optimisation’s (SWO) effectiveness and execution speed by incorporating two additional steps of Selection and Mutation which implement evolution wi...
| Main Authors: | , , |
|---|---|
| Format: | Conference or Workshop Item |
| Published: |
2006
|
| Online Access: | https://eprints.nottingham.ac.uk/577/ |
| _version_ | 1848790435206529024 |
|---|---|
| author | Aickelin, Uwe Burke, Edmund Li, Jingpeng |
| author_facet | Aickelin, Uwe Burke, Edmund Li, Jingpeng |
| author_sort | Aickelin, Uwe |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | This paper presents a technique called Improved Squeaky Wheel Optimisation (ISWO) for driver scheduling problems. It improves the original Squeaky Wheel Optimisation’s (SWO) effectiveness and execution speed by incorporating two additional steps of Selection and Mutation which implement evolution within a single solution. In the ISWO, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The Analysis step first computes the fitness of a current solution to identify troublesome components. The Selection step then discards these troublesome components probabilistically by using the fitness measure, and the Mutation step follows to further discard a small number of components at random. After the above steps, an input solution becomes partial and thus the resulting partial solution needs to be repaired. The repair is carried out by using the Prioritization step to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, the optimisation in the ISWO is achieved by solution disruption, iterative improvement and an iterative constructive repair process performed. Encouraging experimental results are reported. |
| first_indexed | 2025-11-14T18:12:34Z |
| format | Conference or Workshop Item |
| id | nottingham-577 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:12:34Z |
| publishDate | 2006 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-5772020-05-04T20:29:42Z https://eprints.nottingham.ac.uk/577/ Improved Squeaky Wheel Optimisation for Driver Scheduling Aickelin, Uwe Burke, Edmund Li, Jingpeng This paper presents a technique called Improved Squeaky Wheel Optimisation (ISWO) for driver scheduling problems. It improves the original Squeaky Wheel Optimisation’s (SWO) effectiveness and execution speed by incorporating two additional steps of Selection and Mutation which implement evolution within a single solution. In the ISWO, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The Analysis step first computes the fitness of a current solution to identify troublesome components. The Selection step then discards these troublesome components probabilistically by using the fitness measure, and the Mutation step follows to further discard a small number of components at random. After the above steps, an input solution becomes partial and thus the resulting partial solution needs to be repaired. The repair is carried out by using the Prioritization step to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, the optimisation in the ISWO is achieved by solution disruption, iterative improvement and an iterative constructive repair process performed. Encouraging experimental results are reported. 2006 Conference or Workshop Item PeerReviewed Aickelin, Uwe, Burke, Edmund and Li, Jingpeng (2006) Improved Squeaky Wheel Optimisation for Driver Scheduling. In: Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN IX), Reykjavik, Iceland. |
| spellingShingle | Aickelin, Uwe Burke, Edmund Li, Jingpeng Improved Squeaky Wheel Optimisation for Driver Scheduling |
| title | Improved Squeaky Wheel Optimisation for Driver Scheduling |
| title_full | Improved Squeaky Wheel Optimisation for Driver Scheduling |
| title_fullStr | Improved Squeaky Wheel Optimisation for Driver Scheduling |
| title_full_unstemmed | Improved Squeaky Wheel Optimisation for Driver Scheduling |
| title_short | Improved Squeaky Wheel Optimisation for Driver Scheduling |
| title_sort | improved squeaky wheel optimisation for driver scheduling |
| url | https://eprints.nottingham.ac.uk/577/ |