Conventionally, the vehicle routing problem is considered
as a pure delivery or a pickup variant. In many real-life
circumstances, the vehicle is frequently used for a mixed
combination of delivery and pickup. This paper deals with
the vehicle routing problem variant with mixed delivery
and pickup. A two-phase heuristic is developed to address
this variant. A constructive heuristic based on modified
K-means clustering methodology is proposed to develop an
initial feasible solution in the first stage. Then, the
adapted Or-opt mechanism is employed as the improvement
heuristic for improving the initial feasible solution. Random
test instances generated based on real data are evaluated
between the lower bound obtained using CPLEX for the mathematical
programming model developed by Wade and Salhi (2002) and
the solution of the two-stage heuristic.
Logistics is critically considered as a significant factor
of economic activities in any organization. The appropriate
usage of set of vehicles to fulfill the customer service
with the optimal set of routes is known as Vehicle Routing
Problem (VRP) (Laporte and Osman, 1995). The Vehicle Routing
Problem with Backhauls (VRPB) is an extension of VRP which
allows pickup at the end of the delivery tour of the vehicle.
VRPB includes delivery customers called linehaul customers
and pickup customers called backhaul customers. Both the
customers are served from a depot with a set of vehicles
with the condition that all the pickup customers will be
served after delivering the loads to delivery customer.
Among several variants of VRPB, one of the variants which
can also serve backhauls before all linehaul customers is
called VRP with Mixed Delivery and Pickup (VRPMDP). The
VRPMDP is more complicated than the classical VRPB because
of the fluctuating load. In the VRPMDP, the load of the
vehicle can either decrease or increase at each customer
depending on whether the customer has backhaul or linehaul,
respectively. Therefore, it is necessary to ensure that
the vehicle capacity is not exceeded at any arc along the
route. In the classical VRPB, the direction of route for
backhaul customers is fixed once the vehicles cover all
linehaul customers. This is not the case for VRPMDP because
the direction may not essentially be fixed by the insertion
of a backhaul customer; so, the feasibility needs to be
checked in both the directions. This paper proposes a two-stage
heuristic based on modified K-means clustering methodology
and adapted Or-opt mechanism to solve VRPMDP for randomly
generated instances generated based on real data.
|
