2013, 3(4): 665-680. doi: 10.3934/naco.2013.3.665

Semi-definite programming based approaches for real-time tractor localization in port container terminals

1. 

Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong, China, China

2. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

Received  February 2013 Revised  October 2013 Published  October 2013

In order to effectively manage and deploy internal tractors in a port container marine terminal, real-time information concerning the location of the tractors is required so that timely scheduling and planning of tractors control and dispatching can be derived. This paper propose a wireless sensor network-based Truck Flow Management System (TFMS) to help tracking the real-time location of internal tractors in a container terminal so as to streamline the management of the terminal operation. Focusing on the real-time localization, the semi-definite programming (SDP) based approaches are employed by introducing the terminal context information, including prior known road constraints and available time-serial data recorded in the network, into the traditional SDP formulation. Experimental results are presented to show that the proposed formulation and treatments to the problem can greatly decrease the estimated errors compared to the traditional formulation.
Citation: Wei Huang, Ka-Fai Cedric Yiu, Henry Y. K. Lau. Semi-definite programming based approaches for real-time tractor localization in port container terminals. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 665-680. doi: 10.3934/naco.2013.3.665
References:
[1]

A. Y. Alfakih, A. Khandani and H. Wolkowicz, Solving Euclidean distance matrix completion problems via semidefinite programming,, Computational optimization and applications, 12 (1999), 13. doi: 10.1023/A:1008655427845. Google Scholar

[2]

X. Bai, X. Zheng and X. Sun, A survey on probabilistically constrainted optimization problems,, Numerical Algebra, 2 (2012), 767. doi: 10.3934/naco.2012.2.767. Google Scholar

[3]

P. Biswas, T.C. Liang, K.C. Toh, Y. Ye and T.C. Wang, Semidefinite programming approaches for sensor network localization with noisy distance measurements,, IEEE transactions on automation science and engineering, 3 (2006), 360. Google Scholar

[4]

P. Biswas, T. C. Liang, T. C. Wang and Y. Ye, Semidefinite programming based algorithms for sensor network localization,, ACM Transactions on Sensor Networks, 2 (2006), 188. Google Scholar

[5]

P. Biswas, K. C. Toh and Y. Ye, A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation,, SIAM Journal on Scientific Computing, 30 (2007), 1251. doi: 10.1137/05062754X. Google Scholar

[6]

P. Biswas and Y. Ye, Semidefinite programming for ad hoc wireless sensor network localization,, in, (2004), 46. Google Scholar

[7]

J.A. Costa, N. Patwari, and A.O. Hero, III, Distributed weighted-multidimensional scaling for node localization in sensor networks,, ACM Transactions on Sensor Networks, 2 (2006), 39. Google Scholar

[8]

L. Doherty, K. S. J. Pister and L. El Ghaoui, Convex position estimation in wireless sensor networks,, in, (2001), 1655. Google Scholar

[9]

T. Eren, O. K. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson and P. N. Belhumeur, Rigidity, computation, and randomization in network localization,, in, (2004), 2673. Google Scholar

[10]

D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin and S. Wicker, "An Empirical Study of Epidemic Algorithms in Large Scale Multihop Wireless Networks,", Intel Corporation, (2002). Google Scholar

[11]

M. Gerdts, R. Henrion, D. Homberg and C. Landry, Path planning and collision avoidance for robots,, Numerical Algebra, 2 (2012), 437. doi: 10.3934/naco.2012.2.437. Google Scholar

[12]

A. A. Kannan, G. Mao and B. Vucetic, Simulated annealing based localization in wireless sensor network,, in, (2005), 513. Google Scholar

[13]

S. Kim, M. Kojima and H. Waki, Exploiting sparsity in SDP relaxation for sensor network localization,, SIAM Journal on Optimization, 20 (2009), 192. doi: 10.1137/080713380. Google Scholar

[14]

J. Lofberg, YALMIP: A toolbox for modeling and optimization in MATLAB,, in Proc. Int. Symp. CACSD, (2004), 284. Google Scholar

[15]

K. W. K. Lui, W. K. Ma, H. C. So and F. K. W. Chan, Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed,, IEEE Transactions on Signal Processing, 57 (2009), 752. doi: 10.1109/TSP.2008.2007916. Google Scholar

[16]

J. J. Mor and Z. Wu, Global continuation for distance geometry problems,, SIAM Journal on Optimization, 7 (1997), 814. doi: 10.1137/S1052623495283024. Google Scholar

[17]

E. Niewiadomska-Szynkiewicz and M. Marks, Optimization schemes for wireless sensor network localization,, International Journal of Applied Mathematics and Computer Science, 19 (2009), 291. Google Scholar

[18]

R. W. Ouyang, A. K. Wong and C. T. Lea, Received signal strength-based wireless localization via semidefinite programming: noncooperative and cooperative schemes,, IEEE Transactions on Vehicular Technology, 59 (2010), 1307. Google Scholar

[19]

A. M. C. So and Y. Ye, Theory of semidefinite programming for sensor network localization,, Mathematical Programming, 109 (2007), 367. doi: 10.1007/s10107-006-0040-1. Google Scholar

[20]

D. Steenken, S. Vos and R. Stahlbock, Container terminal operation and operations research - a classification and literature review,, OR Spectrum, 26 (2004), 3. doi: 10.1007/s00291-007-0100-9. Google Scholar

[21]

J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,, Optimization Methods and Software, 11 (1999), 625. doi: 10.1080/10556789908805766. Google Scholar

[22]

J. Sun, On methods for solving non-linear semidefinite optimization problems,, Numerical Algebra, 1 (2011), 1. doi: 10.3934/naco.2011.1.1. Google Scholar

[23]

K. C. Toh, M. J. Todd and R. H. Tutuncu, SDPT3 - a Matlab software package for semidefinite programming,, Optimization Methods and Software, 11 (1999), 545. doi: 10.1080/10556789908805762. Google Scholar

[24]

P. Tseng, Second-order cone programming relaxation of sensor network localization,, SIAM Journal on Optimization, 18 (2008), 156. doi: 10.1137/050640308. Google Scholar

[25]

H. Waki, S. Kim, M. Kojima and M. Muramatsu, Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity,, SIAM Journal on Optimization, 17 (2006), 218. doi: 10.1137/050623802. Google Scholar

[26]

S. Y. Wang and Y. W. Li, Evaluation of intelligent traffic signal control algorithms under realistic landmark-based traffic pattern over the NCTUns network simulator,, in, (2012), 379. Google Scholar

[27]

Z. Wang, S. Zheng, S. Boyd and Y. Ye, Further relaxations of the SDP approach to sensor network localization,, SIAM Journal on Optimization, 19 (2008), 655. doi: 10.1137/060669395. Google Scholar

[28]

S. Zhang, J. Cao, L. Chen and D. Chen, Accurate and energy-efficient range-free localization for mobile sensor networks,, IEEE Transactions on Mobile Computing, 9 (2010), 897. Google Scholar

show all references

References:
[1]

A. Y. Alfakih, A. Khandani and H. Wolkowicz, Solving Euclidean distance matrix completion problems via semidefinite programming,, Computational optimization and applications, 12 (1999), 13. doi: 10.1023/A:1008655427845. Google Scholar

[2]

X. Bai, X. Zheng and X. Sun, A survey on probabilistically constrainted optimization problems,, Numerical Algebra, 2 (2012), 767. doi: 10.3934/naco.2012.2.767. Google Scholar

[3]

P. Biswas, T.C. Liang, K.C. Toh, Y. Ye and T.C. Wang, Semidefinite programming approaches for sensor network localization with noisy distance measurements,, IEEE transactions on automation science and engineering, 3 (2006), 360. Google Scholar

[4]

P. Biswas, T. C. Liang, T. C. Wang and Y. Ye, Semidefinite programming based algorithms for sensor network localization,, ACM Transactions on Sensor Networks, 2 (2006), 188. Google Scholar

[5]

P. Biswas, K. C. Toh and Y. Ye, A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation,, SIAM Journal on Scientific Computing, 30 (2007), 1251. doi: 10.1137/05062754X. Google Scholar

[6]

P. Biswas and Y. Ye, Semidefinite programming for ad hoc wireless sensor network localization,, in, (2004), 46. Google Scholar

[7]

J.A. Costa, N. Patwari, and A.O. Hero, III, Distributed weighted-multidimensional scaling for node localization in sensor networks,, ACM Transactions on Sensor Networks, 2 (2006), 39. Google Scholar

[8]

L. Doherty, K. S. J. Pister and L. El Ghaoui, Convex position estimation in wireless sensor networks,, in, (2001), 1655. Google Scholar

[9]

T. Eren, O. K. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson and P. N. Belhumeur, Rigidity, computation, and randomization in network localization,, in, (2004), 2673. Google Scholar

[10]

D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin and S. Wicker, "An Empirical Study of Epidemic Algorithms in Large Scale Multihop Wireless Networks,", Intel Corporation, (2002). Google Scholar

[11]

M. Gerdts, R. Henrion, D. Homberg and C. Landry, Path planning and collision avoidance for robots,, Numerical Algebra, 2 (2012), 437. doi: 10.3934/naco.2012.2.437. Google Scholar

[12]

A. A. Kannan, G. Mao and B. Vucetic, Simulated annealing based localization in wireless sensor network,, in, (2005), 513. Google Scholar

[13]

S. Kim, M. Kojima and H. Waki, Exploiting sparsity in SDP relaxation for sensor network localization,, SIAM Journal on Optimization, 20 (2009), 192. doi: 10.1137/080713380. Google Scholar

[14]

J. Lofberg, YALMIP: A toolbox for modeling and optimization in MATLAB,, in Proc. Int. Symp. CACSD, (2004), 284. Google Scholar

[15]

K. W. K. Lui, W. K. Ma, H. C. So and F. K. W. Chan, Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed,, IEEE Transactions on Signal Processing, 57 (2009), 752. doi: 10.1109/TSP.2008.2007916. Google Scholar

[16]

J. J. Mor and Z. Wu, Global continuation for distance geometry problems,, SIAM Journal on Optimization, 7 (1997), 814. doi: 10.1137/S1052623495283024. Google Scholar

[17]

E. Niewiadomska-Szynkiewicz and M. Marks, Optimization schemes for wireless sensor network localization,, International Journal of Applied Mathematics and Computer Science, 19 (2009), 291. Google Scholar

[18]

R. W. Ouyang, A. K. Wong and C. T. Lea, Received signal strength-based wireless localization via semidefinite programming: noncooperative and cooperative schemes,, IEEE Transactions on Vehicular Technology, 59 (2010), 1307. Google Scholar

[19]

A. M. C. So and Y. Ye, Theory of semidefinite programming for sensor network localization,, Mathematical Programming, 109 (2007), 367. doi: 10.1007/s10107-006-0040-1. Google Scholar

[20]

D. Steenken, S. Vos and R. Stahlbock, Container terminal operation and operations research - a classification and literature review,, OR Spectrum, 26 (2004), 3. doi: 10.1007/s00291-007-0100-9. Google Scholar

[21]

J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,, Optimization Methods and Software, 11 (1999), 625. doi: 10.1080/10556789908805766. Google Scholar

[22]

J. Sun, On methods for solving non-linear semidefinite optimization problems,, Numerical Algebra, 1 (2011), 1. doi: 10.3934/naco.2011.1.1. Google Scholar

[23]

K. C. Toh, M. J. Todd and R. H. Tutuncu, SDPT3 - a Matlab software package for semidefinite programming,, Optimization Methods and Software, 11 (1999), 545. doi: 10.1080/10556789908805762. Google Scholar

[24]

P. Tseng, Second-order cone programming relaxation of sensor network localization,, SIAM Journal on Optimization, 18 (2008), 156. doi: 10.1137/050640308. Google Scholar

[25]

H. Waki, S. Kim, M. Kojima and M. Muramatsu, Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity,, SIAM Journal on Optimization, 17 (2006), 218. doi: 10.1137/050623802. Google Scholar

[26]

S. Y. Wang and Y. W. Li, Evaluation of intelligent traffic signal control algorithms under realistic landmark-based traffic pattern over the NCTUns network simulator,, in, (2012), 379. Google Scholar

[27]

Z. Wang, S. Zheng, S. Boyd and Y. Ye, Further relaxations of the SDP approach to sensor network localization,, SIAM Journal on Optimization, 19 (2008), 655. doi: 10.1137/060669395. Google Scholar

[28]

S. Zhang, J. Cao, L. Chen and D. Chen, Accurate and energy-efficient range-free localization for mobile sensor networks,, IEEE Transactions on Mobile Computing, 9 (2010), 897. Google Scholar

[1]

Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial & Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817

[2]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[3]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[4]

Yi Xu, Jinjie Liu, Liqun Qi. A new class of positive semi-definite tensors. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-11. doi: 10.3934/jimo.2018186

[5]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[6]

Stephane Chretien, Paul Clarkson. A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018161

[7]

Monika Eisenmann, Etienne Emmrich, Volker Mehrmann. Convergence of the backward Euler scheme for the operator-valued Riccati differential equation with semi-definite data. Evolution Equations & Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017

[8]

Hema K. Achanta, Soura Dasgupta, Raghuraman Mudumbai, Weiyu Xu, Zhi Ding. Optimum sensor placement for localization of a hazardous source under log normal shadowing. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 361-382. doi: 10.3934/naco.2019024

[9]

Sebastià Galmés. Markovian characterization of node lifetime in a time-driven wireless sensor network. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 763-780. doi: 10.3934/naco.2011.1.763

[10]

Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473

[11]

Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics & Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471

[12]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[13]

Simone Göttlich, Stephan Knapp. Semi-Markovian capacities in production network models. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3235-3258. doi: 10.3934/dcdsb.2017090

[14]

Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059

[15]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439

[16]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013

[17]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial & Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1

[18]

Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure & Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167

[19]

Jaedal Jung, Ertugrul Taciroglu. A divide-alternate-and-conquer approach for localization and shape identification of multiple scatterers in heterogeneous media using dynamic XFEM. Inverse Problems & Imaging, 2016, 10 (1) : 165-193. doi: 10.3934/ipi.2016.10.165

[20]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

 Impact Factor: 

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]