  During natural or anthropogenic disasters, humanitarian organizations face a
series of time-sensitive tasks. One of the tasks involves picking up critical
resources (e.g., first aid kits, blankets, water) from warehouses and
delivering them to the affected people. To successfully deliver these items to
the people in need, the organization needs to make decisions that range from
the quick acquisition of vehicles from the local market, to the preparation of
pickup and delivery schedules and vehicle routes. During crises, the supply of
vehicles is often limited, their acquisition cost is steep, and special rental
periods are imposed. At the same time, the affected area needs the aid
materials as fast as possible, and deliveries must be made within due time.
Therefore, it is imperative that the decisions of acquiring, scheduling, and
routing of vehicles are made optimally and quickly. In this paper, we consider
a variant of a truckload open vehicle routing problem with time windows, which
is suitable for modeling vehicle routing operations during a humanitarian
crisis. We present two integer linear programming models to formulate the
problem, with the first one being an arc-based mixed integer linear programming
model. The second model is a path-based integer linear programming model, for
which we design two fast path generation algorithms. The first model is solved
exactly using the commercial solver, while we propose to solve the second model
within a column generation framework. Finally, we perform numerical experiments
and compare the results obtained from the two models. We show that the
path-based model, when solved with our column generation algorithm, outperforms
the arc-based model in terms of solution time without sacrificing the solution
quality.
