Mathematics and Computer Science, Volume 2

16Quickest Multi-Commodity Contraflow with Non-Symmetric Traversal Times

Shiva Prakash Gupta^1⋆, Urmila Pyakurel² and Tanka Nath Dhamala²

¹Tri-Chandra Multiple Campus, Tribhuvan University, Kathmandu, Nepal

²Central Department of Mathematics, Tribhuvan University, Kathmandu, Nepal

Abstract

Routing multiple distinct commodities from particular supply points to appropriate destination points via the arcs of a network topology while preserving capacity limits is the most challenging issue in operations research. The quickest multi-commodity flow issue reduces the delivery time to complete the process. Computationally, this problem is NP-hard. We consider asymmetric transit times on anti-parallel lanes due to uneven road conditions and flow dependency. Outbound lane capacity can be boosted by reorienting lanes towards demand locations. We incorporate the contraflow strategy to the quickest multi-commodity flow problem and provide an approximation scheme utilizing length-bounded flow with non-symmetric traversal times on oppositely oriented lanes.

Keywords: Network flow, quickest multi-commodity, contraflow, non-symmetric traversal times, length-bound

16.1 Introduction

The topology of a transport system is described as a network that correlates to the transshipment of diverse commodities, with distribution centers, demand centers, and intersections of road segments serving as nodes and arcs serving as linkages between nodes. The starting and ending destinations of commodities are ...