Premium
The mixed capacitated general routing problem with time‐dependent demands
Author(s) -
Ahabchane Chahid,
Langevin André,
Trépanier Martin
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21984
Subject(s) - mathematical optimization , metaheuristic , computer science , integer programming , routing (electronic design automation) , set (abstract data type) , graph , mathematics , theoretical computer science , computer network , programming language
The mixed capacitated general routing problem (MCGRP) is defined over a mixed graph, for which some nodes, arcs, and edges must be serviced. The problem consists of determining a set of routes of minimum cost that satisfy the demand. Some problems like salt spreading have a time‐dependent demand which was ignored in the previous studies. This variation of demand is due to the weather or traffic conditions. This study presents a mixed integer programming model without graph transformation to node routing. We use CPLEX to solve small instances and we develop a Slack Induction by String Removals metaheuristic for large instances adapted to this problem. The proposed model and metaheuristic were tested on problems derived from a set of classical instances of the MCGRP with some modifications to include time‐dependent demands.