Algorithms for multi-trip vehicle routing and device to device communications
Date
2022
Authors
Karimi, Leila
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta. : Dept. of Mathematics and Computer Science
Abstract
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.
Description
Keywords
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