Algorithms for multi-trip vehicle routing and device to device communications

Thumbnail Image
Karimi, Leila
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Lethbridge, Alta. : Dept. of Mathematics and Computer Science
Motivated by the transportation needs of modern-day retailers, we consider a variant of the vehicle routing problem with time windows in which each truck has a variable capacity. In our model, each vehicle can bring one or more wagons. The clients are visited within specified time windows, and the vehicles can also make multiple trips. We give a math- ematical programming formulation for the problem and a branch and price algorithm is used to solve the model. In each iteration of branch and price, column generation is ap- plied. Based on the different capacities, different subproblems are created to find the best column. We extend Solomon’s instances to evaluate our approach. We report on the com- putational results using concert technology in CPLEX. Ours is the first such study to the best of our knowledge. For the second part of the thesis, we study the sharing of spec- trum in the device-to-device (D2D) communications in an underlay cellular network. Our model maximizes the total sum-rate such that i) each D2D link is assigned at most one sub-channel, ii) the total interference is at most the required maximum. Our model can also minimize the interference subject to i) the total sum-rate being bounded by some required amount. We give a branch-n-cut algorithm for solving both models. We give a Lagrangian relaxation which is solved optimally and combinatorially for the minimization objective. We give an iterative rounding algorithm that achieves at least a quarter of the optimal sum rate and no more than the required maximum of the total interference when the objective is to maximize sum-rate. Detailed experiments are performed on synthetic as well as net- work simulator data. Our experiments establish the effectiveness of the branch-n-cut and the iterative rounding approach for channel assignment. This thesis is a study on the use of branch and cut, branch and price, and iterative rounding for solving two real world optimization problems.
vehicle routing problem , branch and price , device to device communications , iterative rounding algorithm , Vehicle routing problem , Algorithms , Mathematical optimization , Business logistics--Mathematical models , Combinatorial optimization , Wireless communication systems--Management , Radio resource management (Wireless communications) , Mobile communication systems , Dissertations, Academic