Information Technology Reference
In-Depth Information
location, the clients are partitioned into two regions North and South. Clients
in each region should be visited within a predefined planning horizon. Labor
agreements define, for each day from Monday to Friday, a minimum rest period
of 12 hours starting between 7 pm and 9 pm and a rest period of 24 hours on
Saturday and on Sunday. Thus, every Friday the sales representative returns
to his home city, Lisbon, where he stays during the weekend. Monday morning
he continues his appointments until all clients have been visited or, again, he
returns home for the weekend. Taking into account the clients's time windows
and the rest periods, the salesman has to schedule the visits to clients in order
to minimize the traveled distance (fuel consumption) as well as the completion
time (to return home as soon as possible).
This real-life application may be viewed as a TSPSNTW where the set of
clients defines the set of mandatory cities and the rest periods, including week-
ends, correspond to the selective cities. Clients share the same set of time win-
dows, one for each day from Monday through Friday. The multiple time windows
for clients state that each visit to a client should start between 9 am and 5 pm,
to ensure that it finishes before 7 pm. Time windows for rest periods guarantee
that each rest period starts between 7 pm and 9 pm. The number of rest pe-
riods, i.e., the number of selective cities that should be visited, is given by the
number of nights away from the home city and it is not known in advance, since
it depends on the route duration.
The current economy of the country makes the competition between sales rep-
resentatives even harder than usual. Consequently, the salesman we are working
with was not keen in identifying and giving us the exact location of his clients
as well as he did not allow us to reveal the brands he represents. Therefore,
taking into account his information we have considered 15 North clients and 10
South clients and we randomly generated their location from a predefined set of
cities. Regarding the distances between clients we have considered tabled road
distances. The visit duration depends on the client and was set based on the in-
formation given by the sales representative. Additionally, we set
=15minutes
as a buffer time on each client visit. Regarding the rest periods, we considered
that the sales representative can rest in any of the client location cities, without
taking into account some personal preferences for rest locations. We set
λ
1
=2
and
λ
2
= 1 in the objective function (1). Since this is a small instance problem,
the dimension of the arc set is not large, we skipped the pre-processing phase.
For this application, in the first step of the heuristic branch-and-bound, we
also realized that fixing the value of just one
XEP
decision variable was a
good option to reach “good” quality integer solutions. If an optimal solution
is not reached, in the second step we pick the best feasible solution obtained
and look to daily routes where the sales representative visits three, or more,
mandatory clients. For each of these daily routes, we fix to one the corresponding
decision variables in subset
XEE
and rerun the branch-and-bound. Table 2
shows computational results for each geographical region. To assess the quality
of these solutions we run cplex for two days (172800s), without fixing any decision
variable, and present the corresponding solutions,
Sol
0
N
and
Sol
0
S
.
Sol
1
∗
and
