TY - JOUR

T1 - Solving the Team Orienteering Arc Routing Problem with a column generation approach

AU - Riera-Ledesma, Jorge

AU - Jose Salazar-Gonzalez, Juan

PY - 2017/10/1

Y1 - 2017/10/1

N2 - The Team Orienteering Arc Routing Problem is a variation of the so-called Team Orienteering Problem where the customers are associated with the arcs of a directed graph. A fleet of uncapacitated vehicles, located at a depot, must give service to a set of regular customers, while another set of optional customers is available to be potentially serviced. Each optional customer generates a profit that is collected if it is serviced. Although the customers may be visited several times by one or more vehicles, its associated profit is collected at most once. The problem aims at designing vehicle routes with a time duration not longer than a pre-specified time limit, serving all regular customers and some of the optional customers to maximize the total profit collected.Very recently, a commodity-flow model and a branch-and-cut approach have been published to solve this problem. Motivated by the weak dual bounds produced by the Linear-Programing relaxation of the knapsack constraints establishing the time limit for the routes, we propose a new approach based on column generation. As a first step we transform the original customer-on-arc representation into a customer-on-7 vertex representation. This transformation leads to a model using binary variables rather than integer variables, thus simplifying the branching phase of our algorithm. It also simplifies the pricing phase since the contribution of a route to the objective function depends only on the customers in the route and not on their sequence. We propose a set-partitioning formulation and two column-generation algorithms.Our proposal has been shown to be useful in those cases where the previous branch-and-cut algorithm shows poor performance, that is, in those instances with a significant influence of the knapsack constraint. Thus, the column generation algorithm becomes a complementary approach to the branch-and cut algorithm. (C) 2017 Elsevier B.V. All rights reserved.

AB - The Team Orienteering Arc Routing Problem is a variation of the so-called Team Orienteering Problem where the customers are associated with the arcs of a directed graph. A fleet of uncapacitated vehicles, located at a depot, must give service to a set of regular customers, while another set of optional customers is available to be potentially serviced. Each optional customer generates a profit that is collected if it is serviced. Although the customers may be visited several times by one or more vehicles, its associated profit is collected at most once. The problem aims at designing vehicle routes with a time duration not longer than a pre-specified time limit, serving all regular customers and some of the optional customers to maximize the total profit collected.Very recently, a commodity-flow model and a branch-and-cut approach have been published to solve this problem. Motivated by the weak dual bounds produced by the Linear-Programing relaxation of the knapsack constraints establishing the time limit for the routes, we propose a new approach based on column generation. As a first step we transform the original customer-on-arc representation into a customer-on-7 vertex representation. This transformation leads to a model using binary variables rather than integer variables, thus simplifying the branching phase of our algorithm. It also simplifies the pricing phase since the contribution of a route to the objective function depends only on the customers in the route and not on their sequence. We propose a set-partitioning formulation and two column-generation algorithms.Our proposal has been shown to be useful in those cases where the previous branch-and-cut algorithm shows poor performance, that is, in those instances with a significant influence of the knapsack constraint. Thus, the column generation algorithm becomes a complementary approach to the branch-and cut algorithm. (C) 2017 Elsevier B.V. All rights reserved.

KW - Travelling salesman

KW - Orienteering Problem

KW - Vehicle routing problem

KW - Branch-and-price-and-cut

KW - MAXIMUM COLLECTION PROBLEM

KW - CUT-AND-PRICE

KW - ALGORITHM

U2 - 10.1016/j.ejor.2017.03.027

DO - 10.1016/j.ejor.2017.03.027

M3 - Journal article

VL - 262

SP - 14

EP - 27

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -