The Skill Vehicle Routing Problem

详细信息    查看全文

• 作者：Paola Cappanera (1) paola.cappanera@unifi.it
  Luís Gouveia (2) legouveia@fc.ul.pt
  Maria Grazia Scutellà (3) scut@di.unipi.it
• 刊名：Lecture Notes in Computer Science
• 出版年：2011
• 出版时间：2011
• 年：2011
• 卷：6701
• 期：1
• 页码：354-364
• 全文大小：191.9 KB
• 参考文献：1. Agnihothri, S.R., Mishra, A.K.: Cross-training decisions in field services with three job types and server-job mismatch. Decision Sciences 35(2), 239–257 (2004)
  2. Baldacci, R., Bartolini, E., Mingozzi, A., Roberti, R.: An exact solution framework for a broad class of vehicle routing problems. Computational Managagement Science 7, 229–268 (2010)
  3. Baldacci, R., Bartolini, E., Mingozzi, A., Valletta, A.: An exact algorithm for the period routing problem. Operations Research (to appear, 2011)
  4. Baldacci, R., Toth, P., Vigo, D.: Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operations Research 175, 213–245 (2009)
  5. Borsani, V., Matta, A., Beschi, G., Sommaruga, F.: A home care scheduling model for human resources. In: IEEE International Conference on Service Systems and Service Management, pp. 449–454 (2006)
  6. Cordeau, J.F., Laporte, G.: A tabu search algorithm for the site dependent vehicle routing problem with time windows. INFOR 39(3), 292–298 (2001)
  7. Rapaccini, M., Sistemi, A., Visintin, F.: A simulation-based DSS for field service delivery optimization. In: Proceedings of the International Workshop on Modelling and Applied Simulation, Campora San Giovanni, Amantea (CS), Italy, pp. 116–122 (2008)
• 作者单位：1. Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Firenze, Italy2. Departamento de Estatística e Investiga??o Operacional, Universidade de Lisboa, Lisboa, Portugal3. Dipartimento di Informatica, Università di Pisa, Pisa, Italy
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Given a (complete) directed network, where a skill level s _j is associated with each node j other than the depot, stating requirements for the associated service call, and given a set of available technicians, each one operating at a certain skill level, we address the problem of defining the tour of each technician, each one starting and ending at the depot, in such a way that each service requirement is fulfilled by exactly one technician, and proper skill level constraints are satisfied. These constraints state that the service requirement at node j can be operated by any technician having a skill level at least s _j . Given travelling costs for the arcs of the network, which are skill level dependent, we want to determine a minimum cost set of tours which satisfy the skill level constraints. This problem, named Skill VRP, originates from a real application context and it specializes, to some extents, the Site Dependent VRP (SDVRP) and, thus, the Periodic VRP. Furthermore, it shows strict relationships with Home Care Scheduling problems. Various ILP formulations are proposed for Skill VRP, which are tested on a large suite of randomly generated instances. The obtained results show that the stated problem may be very difficult to solve exactly. However, some of the proposed models produce LP bounds which are very close to the optimum cost, and which can be determined in an efficient way. Thus, these ILP models constitute a very promising starting point for the solution of Skill VRP, and for the design of efficient cutting plane approaches for real application extensions.