Iterated local search for workforce scheduling and routing problems
| Autor: | Tolga Bektaş, Fulin Xie, Chris N. Potts |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Workforce scheduling
Mathematical optimization 021103 operations research Control and Optimization Computer Networks and Communications Total cost Computer science Iterated local search Computation 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Scheduling (computing) Artificial Intelligence Vehicle routing problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Destination-Sequenced Distance Vector routing Special case Software Information Systems |
| Popis: | The integration of scheduling workers to perform tasks with the traditional vehicle routing problem gives rise to the workforce scheduling and routing problems (WSRP). In the WSRP, a number of service technicians with different skills, and tasks at different locations with pre-defined time windows and skill requirements are given. It is required to find an assignment and ordering of technicians to tasks, where each task is performed within its time window by a technician with the required skill, for which the total cost of the routing is minimized. This paper describes an iterated local search (ILS) algorithm for the WSRP. The performance of the proposed algorithm is evaluated on benchmark instances against an off-the-shelf optimizer and an existing adaptive large neighbourhood search algorithm. The proposed ILS algorithm is also applied to solve the skill vehicle routing problem, which can be viewed as a special case of the WSRP. The computational results indicate that the proposed algorithm can produce high-quality solutions in short computation times. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|