EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
800. Logic-Based Benders Decomposition for a Capacitated Vehicle Routing Problem With a Zone Tariff
Invited abstract in session TD-58: MILPs for Vehicle Routing 1, stream VeRoLog - Vehicle Routing and Logistics.
Tuesday, 14:30-16:00Room: S07 (building: 101)
Authors (first author is the speaker)
| 1. | Niklas Tuma
|
| Technical University of Munich | |
| 2. | Alexander Hübner
|
| Supply and Value Chain Management, Technical University Munich | |
| 3. | Manuel Ostermeier
|
| University of Augsburg |
Abstract
For the cost-efficient supply of stores, it is common in retail practice to rely on third-party logistics providers (3PL) instead of their an fleet. A 3PL carries out the retailers' delivery tours and commonly bills according to a zone-based tariff. This tariff assigns each store to one zone that reflects the travel distances for the delivery. Stores further from the depot are assigned to higher zones. The cost of a tour depends on the furthest zone visited and the volume, subject to discounts. Additionally, 3PLs limit the detour of a tour to ensure economic feasibility. The detour limitation prevents excessive driving within the zones visited. While using 3PLs and their zone tariffs reduces the complexity for retailers, the question arises of how retailers can plan cost-minimal tours that are economical for 3PLs. We address this issue and formalize the problem as a Capacitated Vehicle Routing Problem with a Zone Tariff. The nonlinear tariff and the non-monotonically increasing detour drive the complexity. We provide the first mixed-integer formulation (MIP) for the problem, which we strengthen with valid inequalities. We develop a logic-based Benders decomposition algorithm (LBBD) to solve larger instances and improve it with problem-specific acceleration techniques. In our numerical experiments, we solve a real-world case and adapted instances from the literature. The LBBD approach reduces the runtime compared to the MIP by up to one order of magnitude.
Keywords
- Transportation
- Vehicle Routing
- Mathematical Programming
Status: accepted
Back to the list of papers