We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK


97% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Polyhedral theory for arc routing problems
View graph of relations

« Back

Polyhedral theory for arc routing problems

Research output: Contribution in Book/Report/ProceedingsChapter (peer-reviewed)


Publication date2000
Host publicationArc routing : theory, solutions and applications
Place of publicationDordrecht
PublisherKluwer Academic Publishers
Number of pages32
ISBN (Print)0792378989
<mark>Original language</mark>English


As explained in Chapter 4, most realistic Arc Routing Problems are known to be NP-hard. Therefore we can expect that there will be certain instances which are impossible to solve to optimality within a reasonable time. However, this does not mean that all instances will be impossible to solve. It may well be that an instance which arises in practice has some structure which makes it amenable to solution by an optimization algorithm. Since, in addition, significant costs are often involved in realworld instances, research into devising optimization algorithms is still regarded as important.

Related projects