An Application of Late Acceptance Hill-Climbing to the Traveling Purchaser Problem - Computational Logistics - page 177

namely l -ConsecutiveDrop and a step for restoring feasibility if needed. For l -
ConsecutiveDrop l markets are selected according to an estimation of the trade-
off between the travel cost reduction occuring by dropping the l markets and
the increase in purchasing costs due to the fact that the products that were pur-
chased in the dropped l markets have to be bought elsewhere. These trade-off
evaluations are performed for each possible path consisting of l +1 consecutive
edges belonging to the initial tour. The different paths are ranked according to
the travel cost reduction minus the purchase costs increase and the path with the
highest rank is dropped. After dropping the l markets NN is applied to reduce
the travel costs of the new (possibly infeasible) tour σ .
If feasibility has to be restored, new markets are added. To guarantee the
generation of a diverse neighborhood only markets are permitted to be added
that have not been in the initial feasible tour. The restore feasibility step proceeds
with computing subsets of permitted markets ( V p ⊆ V ). For the capacitated

TPP the non-satisfied amount of each product k in the infeasible tour has to
be calculated and only subsets of markets are permitted that are selling the
required quantity of product k needed to restore feasibility. For each market
i

V p the travel cost increase ( ρ ( i,σ )), describing the increase in travel costs if
market i is added to σ , and the decrease in purchasing costs ( μ ( i,σ )) for adding
i is computed as product k may be available at a cheaper price at market i .
Markets in the selected subset V p are added one after another according to their
trade-off between travel cost increase and purchase cost decrease. Finally, we
apply LAHC to possibly re-optimize the obtained tour.

∈

3.3 LAHC Algorithms

The general approach of the LAHC algorithms starts with the calculation of an
initial solution. Afterwards the length of the fitness array L fa andaninitial l are
specified. An inner loop performs an iterative procedure to remove l -consecutive
markets from the initial tour σ .Iftheremovalofthe l markets leads to an
infeasible tour the following add procedure grants that the feasibility is restored.
This procedure randomly adds markets from a list of earlier dropped markets at
random position within the tour of the candidate solution. To discourage staying
at local optima the procedure does not allow the add of markets dropped in the
current iteration. Markets are added until the solution of the candidate tour is
feasible and its penalty can no longer be reduced. Finally, the method LAHCTSP
tries to improve the order of markets in the candidate tour. After building the
neighborhoods LAHC is called. If the cost function value of the candidate f ( σ )
is better or equal to the value of the solution f v with v being the solution at the
beginning of the virtual list the candidate is accepted and replaces f v ;otherwise
it is rejected. DeltaPenalty follows the idea of an incremental evaluation to reduce
CPU time, where only changes in the cost function values are calculated and
compared to changes in cost function value of neighborhood solutions rather
than calculating the complete objective function value in every iteration. After
accepting or rejecting a candidate solution the iteration number I is set to I +1.