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

Simple item page
dc.contributor.authorKarimi, Leila
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGaur, Daya
dc.date.accessioned2022-12-15T19:09:24Z
dc.date.available2022-12-15T19:09:24Z
dc.date.issued2022
dc.degree.levelPh.Den_US
dc.description.abstractMotivated 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.en_US
dc.description.sponsorshipNSERCen_US
dc.identifier.urihttps://hdl.handle.net/10133/6396
dc.language.isoenen_US
dc.proquest.subject0984en_US
dc.proquest.subject0796en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta. : Dept. of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectvehicle routing problemen_US
dc.subjectbranch and priceen_US
dc.subjectdevice to device communicationsen_US
dc.subjectiterative rounding algorithmen_US
dc.subjectVehicle routing problemen_US
dc.subjectAlgorithmsen_US
dc.subjectMathematical optimizationen_US
dc.subjectBusiness logistics--Mathematical modelsen_US
dc.subjectCombinatorial optimizationen_US
dc.subjectWireless communication systems--Managementen_US
dc.subjectRadio resource management (Wireless communications)en_US
dc.subjectMobile communication systemsen_US
dc.subjectDissertations, Academicen_US
dc.titleAlgorithms for multi-trip vehicle routing and device to device communicationsen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
KARIMI_LEILA_PHD_2022.pdf
Size:
1.04 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses