Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/31716
Title: Competitive analysis for the on-line truck transportation problem
Authors: Ma, W
Liu, JNK
Chen, G
You, J 
Keywords: Competitive analysis
K-truck transportation problem
On-line algorithms
Issue Date: 2006
Publisher: Springer
Source: Journal of Global Optimization, 2006, v. 34, no. 4, p. 489-502 How to cite?
Journal: Journal of global optimization 
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.
URI: http://hdl.handle.net/10397/31716
ISSN: 0925-5001
EISSN: 1573-2916
DOI: 10.1007/s10898-005-2849-1
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Aug 15, 2017

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
0
Citations as of Aug 20, 2017

Page view(s)

61
Last Week
4
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.