**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows

Abstract

The Vehicle Routing Problem with Soft Time Windows consists in computing a minimum cost set of routes for a fleet of vehicles of limited capacity that must visit a given set of customers with known demand, with the additional feature that each customer expresses a preference about the time at which the visit should occur. If a vehicle serves the customer out of its specified time window, an additional cost is incurred. Here we consider the case with penalties linearly depending on the time windows violation. We present an exact optimization algorithm for the pricing problem which arises when the vehicle routing problem with soft time windows is solved by column generation. The algorithm exploits bi-directional and bounded dynamic programming with decremental state space relaxation.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Ontological neighbourhood

Related concepts (38)

Related MOOCs (25)

Related publications (37)

Window

A window is an opening in a wall, door, roof, or vehicle that allows the exchange of light and may also allow the passage of sound and sometimes air. Modern windows are usually glazed or covered in some other transparent or translucent material, a sash set in a frame in the opening; the sash and frame are also referred to as a window. Many glazed windows may be opened, to allow ventilation, or closed, to exclude inclement weather. Windows may have a latch or similar mechanism to lock the window shut or to hold it open by various amounts.

Set theory

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole. The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory.

Set (mathematics)

A set is the mathematical model for a collection of different things; a set contains elements or members, which can be mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is the empty set; a set with a single element is a singleton. A set may have a finite number of elements or be an infinite set. Two sets are equal if they have precisely the same elements. Sets are ubiquitous in modern mathematics.

Introduction to optimization on smooth manifolds: first order methods

Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).

Launching New Ventures

Develop your promising idea into a successful business concept proposal, and launch it! Gain practical experience in the key steps of the venture creation process, including marketing and fundraising.

Launching New Ventures

Develop your promising idea into a successful business concept proposal, and launch it! Gain practical experience in the key steps of the venture creation process, including marketing and fundraising.

Localizing the source of an epidemic is a crucial task in many contexts, including the detection of malicious users in social networks and the identification of patient zeros of disease outbreaks. The difficulty of this task lies in the strict limitation ...

Francesco Varrato, Antoine Louis Claude Masson, Eliane Ninfa Blumer, Sitthida Samath, Fantin Reichler, Jérôme Julien Chaptinel

This is a set of 11 1-sheet guides, providing abridged notions, advice and references for quick and practical research data management: #01 Research Data: the basics #02 FAIR Data Principles #03 Cost of Research Data Management #04 File Formats #05 Metadat ...

2019In this note, we study certain sufficient conditions for a set of minimal klt pairs ( X, triangle) with kappa ( X, triangle) = dim( X ) - 1 to be bounded. ...