Profit maximization of TSP through a hybrid algorithm

• New TSPs with costs and times between cities with stay times at cities are formulated.
• An ACO–PSO algorithm is developed and used successively and iteratively one after another.
• A TSP is formulated as a profit maximization problem with crisp expenditure and return.
• Total tour time including travel and stay times is fixed.
• Behavioral studies of TSPs are presented for some numerical data with parametric study.

Here a new model of Traveling Salesman Problem (TSP) with uncertain parameters is formulated and solved using a hybrid algorithm. For this TSP, there are some fixed number of cities and the costs and time durations for traveling from one city to another are known. Here a Traveling Salesman (TS) visits and spends some time in each city for selling the company’s product. The return and expenditure at each city are dependent on the time spent by the TS at that city and these are given in functional forms of t. The total time limit for the entire tour is fixed and known. Now, the problem for the TS is to identify a tour program and also to determine the stay time at each city so that total profit out of the system is maximum. Here the model is solved by a hybrid method combining the Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO). The problem is divided into two subproblems where ACO and PSO are used successively iteratively in a generation using one’s result for the other. Numerical experiments are performed to illustrate the models. Some behavioral studies of the models and convergences of the proposed hybrid algorithm with respect to iteration numbers and cost matrix sizes are presented.

Figure optionsDownload as PowerPoint slide