✦ LIBER ✦

The rural postman problem with deadline classes

✍ Scribed by A.N. Letchford; R.W. Eglese

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 694 KB
Volume: 105
Category: Article
ISSN: 0377-2217
DOI: 10.1016/s0377-2217(97)00090-8

No coin nor oath required. For personal study only.

✦ Synopsis

Vehicle routing problems with general time windows are extremely difficult to solve, tlowever, the time windows in a particular problem may have a special structure which can be exploited. We consider a single-vehicle arc-routing problem in which the arcs are partitioned into deadline classes. It is shown that a cutting-plane approach works well for this problem.

📜 SIMILAR VOLUMES

On crossings, the Crossing Postman Probl

On crossings, the Crossing Postman Problem, and the Rural Postman Problem

✍ Garfinkel, Robert S.; Webb, Ian R. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 1 views

The Rural Postman Problem (RPP), on an undirected network, is a classic edge-routing problem. The Crossing Postman Problem is a generalization which is introduced here. Results are presented on the structure of optimal solutions to both problems. A new formulation for RPP, based on these results, is

Algorithms for the rural postman problem

✍ W.L. Pearn; T.C. Wu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 668 KB

The basic cyclic scheduling problem with

The basic cyclic scheduling problem with deadlines

✍ Philippe Chretienne 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 971 KB

New facets and an enhanced branch-and-cu

New facets and an enhanced branch-and-cut for the min–max K-vehicles windy rural postman problem

✍ Enrique Benavent; Angel Corberán; Isaac Plana; José M. Sanchis 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 278 KB

Random sequencing jobs with deadlines pr

Random sequencing jobs with deadlines problem: Growth of the optimal solution values

✍ Krzysztof Szkatuła 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 550 KB

In the paper an asymptotic value of the sequencing jobs with deadlines (SJD) problem is computed for the case of the random SJD problems. It is assumed that problem coefficients are realizations of independent, uniformly distributed over [O,l) random variables, n --) m with deadlines remaining deter

On easy and hard hereditary classes of g

On easy and hard hereditary classes of graphs with respect to the independent set problem

✍ Vladimir E. Alekseev 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 162 KB

In this paper we introduce the concept of a boundary class, which is a helpful tool for classiÿcation of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class X deÿned by a ÿnite set of forbidden induced subgraphs, the problem is NP-hard