GRASP-Based Memetic Algorithm for Multi-period Technician Routing Problem with Mandatory Assigned Tasks and Selective Tasks
摘要
This paper addresses an industrial application encountered by water distribution companies managing extensive networks, focusing specifically on routing and scheduling of tasks over a multi-day planning horizon. Tasks are categorized into customer request tasks, which must adhere to predefined reservation dates and time windows, and internal tasks related to the company network, characterized by priority and due dates, allowing for flexible daily scheduling. The aim is to simultaneously minimize the total travel distance over the planning horizon and maximize the number of network tasks inserted, ensuring that all customer tasks are scheduled. The solution must consider constraints such as limited technician availability, multiple availability intervals, and maximum daily working hours. Additionally, penalties are incurred for unassigned network tasks. The problem is formulated as a novel variant of the Multi-period Technician Routing and Scheduling Problem with Profits (MPTRSPP). To tackle this problem, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) based on a memetic algorithm in the local search phase. The memetic algorithm uses a giant tour encoding of chromosomes and integrates an extended optimal split method. Computational experiments conducted on real-world instances illustrate the effectiveness of the proposed GRASP approach.