Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Remarks on Invariant Method of the Second-Order Linear Differential Equations with Variable Coefficients Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Vehicle Scheduling Problem on Trees

Authors : Jie Zhou, Tianming Bu, Hong Zhu, Yixiang Chen

Published in: Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we study a subproblem of vehicle scheduling problem, which is in general strongly NP-hard. In this problem, the road map is a tree, the release times and the handling times of all the tasks are zero, the deadlines of all the tasks are all the same, and the vehicle has to return to the root finally. We aim to find an optimal schedule such that the total value of the completed tasks are maximized. We show that this problem is NP-hard, and give a pseudo polynomial time algorithm for this problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Generated Fast of the Aircraft Carrier Dimensions in Preliminary Design
next chapter Reflections on the Enterprise to Change Management Concept: In Perspective of Concept Innovation
Literature
1.
Yu W, Liu Z (2011) Single-vehicle scheduling problems with release and service times on a line. Networks 57(2):128–134MathSciNetMATH
2.
Petersen HL, Larsen A, Madsen OBG (2012) Bjorn Petersen and Stefan Ropke, The Simultaneous Vehicle Scheduling and Passenger Service Problem, Transportation Science August 2012 trsc.1120.0429.
3.
Bodin L, Golden B, Assad A, Ball M (1983) Routing and scheduling of vehicles and crews: The state of the art. Comput Oper Res 10:62–212MathSciNet
4.
Bodin LD (1990) Twenty years of routing and scheduling. Oper Res 39:571–579CrossRef
5.
Nagamochi H, Ohnishi T (2008) Approximating a vehicle scheduling problem with time windows and handling times. Theor Comput Sci 393(1–3):133–146MathSciNetCrossRefMATH
6.
7.
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H Freeman and Company, New YorkMATH
8.
Karuno Y, Nagamochi H, Ibaraki T (1996) Vehicle scheduling on a tree to minimize maximum lateness. J Oper Res Soc Jpn 39:345MathSciNetMATH
9.
Vazirani VV (2001) Approximation Algorithms. Springer-Verlag, BerlinMATH
Metadata
Title
Vehicle Scheduling Problem on Trees
Authors
Jie Zhou
Tianming Bu
Hong Zhu
Yixiang Chen
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Book
Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013

Print ISBN: 978-3-642-37501-9

Electronic ISBN: 978-3-642-37502-6

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-3-642-37502-6_64

Premium Partner

    Image Credits