Competitive analysis for the on-line truck transportation problem

Weimin Ma, James N.K. Liu, Guoqing Chen, Jia You

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

In this paper, the on-line k-truck transportation problem (k-OLTTP) whose objects are to be transported between the vertices of a given graph on which there are k mobile trucks to be scheduled is proposed. It is motivated by the research concerning on-line k-truck problem and on-line transportation problem. The goal is to minimize the makespan which is consumed to complete some on-line request sequence. Some preliminary knowledge is introduced and the model of k-OLTTP is established firstly. Two versions of a special case of k-OLTTP, namely 1-OLTTP, have been studied and some results are obtained. For the first version. Open-1-OLTTP, a lower bound of competitive ratio 2 is presented and two optimal on-line algorithms, Reschedule Strategy (RS) and Lay Over Strategy (LOS) respectively, are analyzed. For the second version. Close-1-OLTTP, a lower bound of competitive ratio 1/2 + 1/2 · √1+4/θ, where 9 is the ratio between the time consumed by the loaded truck and the empty truck to travel the same distance, is also developed and on-line algorithms RS and LOS are proved to have competitive ratio 2. Finally, some interesting remarks concerning OLTTP and its future research are discussed.
Original languageEnglish
Pages (from-to)489-502
Number of pages14
JournalJournal of Global Optimization
Volume34
Issue number4
DOIs
Publication statusPublished - 1 Apr 2006

Keywords

  • Competitive analysis
  • K-truck transportation problem
  • On-line algorithms

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this