Travelling Salesman’s Problem-Based Model Application for Mail Routing and Delivery with Minimal Cost
- April 9, 2023
- Posted by: RSIS
- Categories: Computer Science and Engineering, IJRIAS
International Journal of Research and Innovation in Applied Science (IJRIAS) |Volume VIII, Issue III, March 2023|ISSN 2454-6194
Ndifon Godswill Brendan, Ceasar E. Eko
Department of Computer Science, Faculty of Physical Sciences, University of Calabar, Calabar, Nigeria
Received: 05 March 2023; Accepted: 11 March 2023; Published: 08 April 2023
Abstract:- In ancient history, messages were hand-delivered using a variety of methods, including runners, homing pigeons, and riders on horseback. Before the introduction of mechanized courier services, foot messengers physically ran miles to their destinations. However, over the years, the employed methods have changed for the better, but not optimal enough. As in a traveling salesman problem, a delivery agent has a set of cities to visit, a set of parcels or goods of variable weight, a medium of movement, etc, with the specific objectives to minimize the cost of visiting the cities vis-a-vis the constraints. The problem was reduced to a graph problem and handled by linear programming. The researcher developed a model or a scenario whereby courier mail or goods can be delivered by touring cities, using the constraints available in courier services as in the traveling salesman problem. object-oriented design model was adopted for use. The researcher had to develop a platform, including the Google map tool to view the entire route spread depending on where the courier man intends to visit. The weight of the parcels, location for which the parcel(s) is to be delivered, medium of transport, amount to be paid, longitude, and latitude were also considered to estimate the cost-effectiveness of the dispatch. HTML was used to design the interface while javascript was used to code the system. The result of the study was very revealing as there were indications of the fact that dispatches were anticipated faster by 46% than before. The minimal cost was efficient enough with better optimality and the visual effects on graphs, gave encouraging perceptions for users.
Keywords: Traveling salesman, Mail Routing, Minimal Cost, problem-based Model, Graph Problem, Binary Tree, Algorithm,
I. Introduction
A courier is a person or company that delivers messages, packages, and or mail. Couriers are distinguished from ordinary mail services by features such as speed, security, tracking, signature, specialization, and individualization of express services, which are optional for most everyday mail services. As a premium service, couriers are usually more expensive than standard mail services, and their use is normally limited to packages where one or more of these features are considered important enough to warrant the cost. Courier services operate on all scales, from within specific towns or cities, to regional, national, and global services. Large courier companies include DML, OCS, FedEX, EMS INTERNATIONAL, TNT, UPS, and Aramex. These offer services worldwide, typically via a hub and a spoke model. Therefore, the researcher is trying to model a scenario whereby a courier mail can be delivered by touring cities without repeating any of the cities, without having in mind the constraint of using a binary tree to represent the cities.
II. Review of traveling salesman problem
The Travelling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science and operational research. It focused on optimization. In this context, a better solution often means a cheaper solution. TSP is a mathematical problem. It is most easily expressed as a graph describing the locations of a set of nodes.
The traveling salesman problem was defined in the 1800s by the Irish mathematician W.R Hamilton and by the British mathematician Thomas Kirkman. Hamilton icosian game was a recreational puzzle based on finding a Hamiltonian cycle. The general form of the TSP appears to have been first studied by mathematicians during the 1903s in Vienna and at Harvard, notably by Karl Menger. Menger defines the problem, considers the obvious brute force algorithm, and observes the non-optimality of the nearest neighbor heuristics.
The traveling salesman problem describes a salesman who must travel between N cities. The order in which he does this is something he does not care about, as long as he visits each once during his trip, and finishes where he was t first. Each city is connected by other close by cities, nodes, airplanes, or by road or railway. Each of those links between the cities has one or more weights or the cost attached. The cost describes how difficult it is to traverse this edge on the graph, and may be given, for example, by the cost of an airplane ticket or a train ticket, or perhaps by the length of the edges, or time required to complete the traversal. The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible.
