Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similarly to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all these set-partitioning-based approaches have strong assumptions … Read more

The Robust Bike Sharing Rebalancing Problem: Formulations and a Branch-and-Cut Algorithm

Bike Sharing Systems (BSSs) offer a sustainable and efficient urban transportation solution, bringing flexible and eco-friendly alternatives to city logistics. During their operation, BSSs may suffer from unbalanced bike distribution among stations, requiring rebalancing operations throughout the system. The inherent uncertain demand at the stations further complicates these rebalancing operations, even when performed during downtime. … Read more

The Vehicle Routing Problem with Access Restrictions

To mitigate the negative effect of freight vehicles on urban areas, many cities have implemented road accessibility restrictions, including limited traffic zones, which restrict access to specific areas during certain times of the day. Implementing these zones creates a trade-off between the delivery cost and time, even under the assumption of equal traversal time and … Read more

Fair stochastic vehicle routing with partial deliveries

A common assumption in the models for the vehicle routing problem with stochastic demands is that all demands must be satisfied. This is achieved by including recourse actions in two-stage stochastic programming formulations or by ensuring with a high probability that all demand fits within the vehicle capacity (chance-constrained formulations). In this work, we relax … Read more

Column Elimination for Capacitated Vehicle Routing Problems

We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

A Column Generation Approach for the Lexicographic Optimization of Intra-Hospital Transports

Over the last fewyears, the efficient design of processes in hospitals and medical facilities has received more and more attention, particularly when the improvement of the processes is aimed at relieving theworkload of medical staff. To this end,we have developed a method to determine optimal allocations of intra-hospital transports to hospital transport employees. When optimizing … Read more

Insertion Heuristics for a Class of Dynamic Vehicle Routing Problems

We consider a simple family of dynamic vehicle routing problems, in which we have a fixed fleet of identical vehicles, and customer requests arrive during the route-planning process. For this kind of problem, it is natural to use an insertion heuristic. We test several such heuristics computationally, on two different variants of the problem. It … Read more

The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains … Read more

Routing and resource allocation in non-profit settings with equity and efficiency measures under demand uncertainty

Motivated by food distribution operations for non-profit organizations, we study a variant of the stochastic routing-allocation problem under demand uncertainty, in which one decides the assignment of trucks for demand nodes, the sequence of demand nodes to visit (i.e., truck route), and the allocation of food supply to each demand node. We propose three stochastic … Read more

Minimizing earliness-tardiness costs in supplier networks – A Just-in-time Truck Routing Problem

We consider a routing problem where orders are transported just-in-time from several suppliers to an original equipment manufacturer (OEM). This implies that shipments cannot be picked up before their release date when they are ready at the supplier and should be delivered as close as possible to their due date to the OEM. Every shipment … Read more