The method introduces a structured loop-enumeration strategy within the transportation simplex framework that yields optimal solutions identical to classical methods and achieves comparable or improved performance on average runtime, with clearer benefits on medium-to-large instances where loop redundancy is more pronounced.
Abstract
This paper presents a computational refinement of classical optimality procedures for solving Transportation Problems (TPs). Rather than altering the underlying linear programming formulation, the method introduces a structured loop-enumeration strategy within the transportation simplex framework. Specifically, admissible improvement loops are generated from the current basis (occupied cells) and constrained to include exactly one nonbasic (unoccupied) cell, reducing redundant loop exploration. A formal analysis establishes feasibility preservation, strict descent when an improving loop exists, finite termination, and equivalence with classical optimality conditions via reduced costs. Computational experiments on benchmark problems from literature compare the new method with the Stepping–Stone and MODI methods. To evaluate computational efficiency, all computational experiments were conducted using MATLAB R2022b on a computer equipped with an Intel Core i7 processor (3.20 GHz), 16 GB RAM, running Windows 10 (64-bit), Execution time was measured using MATLAB’s built-in timing functions. Each method was run five times per dataset, and the average CPU execution time (in seconds) was recorded to ensure consistency. Results show that the new approach yields optimal solutions identical to classical methods and achieves comparable or improved performance on average runtime, with clearer benefits on medium-to-large instances where loop redundancy is more pronounced. For small instances, differences are minor and may vary due to implementation overhead. The findings position the method as a practical, verifiable computational refinement for efficient loop selection in transportation simplex implementations.
Commonly used in math to discover the optimal solution to a problem with straight-line goals and limits is the technique of linear programming (LP). One of its first and most important applications is the Transport Problem (TP), which aims to find the best distribution strategy that meets supply and demand without sacrificing cost or time. The issue of transportation are balanced when supply meets demand and imbalanced otherwise. The Time-Minimizing Transportation Problem (TMTP) aims to reduce time spent on transportation. The literature suggests several ways to find an Initial Basic Feasible Solution. However, the quality of these solutions varies across methods and problem instances. Some approaches are computationally simple but often yield poor-quality solutions in terms of minimizing total transportation time. Others require slightly more effort yet provide better results, while a few methods can generate near-optimal or even optimal solutions but involve higher computational complexity. Importantly, no single method guarantees optimality for all transportation problems. In this research, we propose new, efficient algorithms for finding initial basic feasible solutions in both balanced and unbalanced transportation problems, with the primary objective of minimizing transportation time. A comparative study of results obtained by the proposed heuristics against existing methods demonstrates that our approach consistently achieves more efficient and reliable outcomes. The findings indicate that the proposed methods can serve as strong alternatives to traditional approaches, offering both computational efficiency and improved solution quality.
Jagannath University Journal of Science, Volume 12, Number 1, Jun. 2025, pp. 143−158
Farhana Rashid, Naeem Hossain, Jannatul Ferdous Jeba et al.· Jagannath University Journal...· 0 citations
The Stop Number Minimization Problem (SNMP), inspired by an autonomous vehicle service from France, arises when a homogeneous fleet of autonomous vehicles transports cargo and personnel across a circuit of stations. The objective is to satisfy all client requests while minimizing the total number of pickup/dropoff stops made by the vehicles, without violating their maximum capacity. We modeled the SNMP as a Pickup and Delivery Problem on an expanded graph with an ordered structure and solved it via a branch-and-price algorithm. The pricing problem was solved using a labeling algorithm with two distinct dominance rules. Additionally, three types of path elimination were introduced in the pricing algorithm. When branching, two strategies were implemented: SOS and Ryan-Foster. We tested our approach in a setting where each vehicle may perform up to 4 laps on the circuit. Computational experiments indicate that this approach solves instances of equivalent size to those tested in previous works in less time. Furthermore, our approach solved instances with up to 80 requests in the single-lap setting, contrasting previous works that solved instances with up to 50 requests.
Victor Nascimento, Luidi Simonetti· Journal of combinatorial opt...· 0 citations
This paper addresses the Capacitated Coverage Path Planning Problem (CPP) arising in agricultural field operations. It aims to determine an efficient sequence of field tracks to be serviced by an agricultural machine subject to limited onboard capacity and refilling constraints, while minimizing non-working distance. The non-working distance is the length traveled by the machinery not performing productive fieldwork. Optimizing how agricultural machinery maneuvers can help reduce operational costs and greenhouse gas (GHG) emissions, while increasing productivity. The problem is formulated as a variant of the constrained Vehicle Routing Problem (VRP), which is NP-hard. A novel exact Integer Linear Programming (ILP) formulation is proposed. We employ a commercial optimizer, Gurobi, to obtain optimal reference solutions for smaller instances. To overcome scalability limitations, a metaheuristic based on "simulated annealing (SA) methodology" is proposed. Our algorithm incorporates customized neighborhood search operators and a capacity-aware route-splitting mechanism to explicitly handle refilling operations. Computational experiments are conducted on real-world field instances. The proposed metaheuristic is evaluated against the exact formulation. The results indicate that SA consistently produces near-optimal solutions with substantially reduced computation times.
Fabliha Zahin, Shahadat Hossain· Annual Conference on Genetic...· 0 citations
This study introduces a novel constrained multi-objective evolutionary algorithm, termed DPCME, which employs two interacting populations that exchange information, enabling effective global exploration and reducing the risk of convergence to local optima.
Sequencing and timing decisions frequently arise interdependently in combinatorial optimization problems. This study concerns a speed optimization problem (SOP) that determines optimal speeds to minimize a strictly convex cost function on a fixed sequence of nodes with time window constraints and a joint routing and speed optimization problem, finding an optimal sequence of nodes and speeds on each route. The paper describes two polynomial-time algorithms for the SOP, one to solve the SOP and another to compute all possible completion times for a sequence, along with proofs of optimality, and a branch-and-price algorithm, incorporating a new dominance rule, for the joint routing and speed optimization problem. Computational experiments show the proposed algorithm achieves an average 17.5-fold improvement in computational time over the state-of-the-art for benchmark instances solved to optimality (ranging from 4.9-fold on road to 73-fold on maritime instances).
History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1047 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.1047 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
Stefan Schaudt, T. Bektaş· INFORMS journal on computing· 0 citations
The job sequencing and tool switching problem with non-identical parallel machines (SSP-NPM) is a challenging combinatorial optimization problem that arises in flexible manufacturing systems. It jointly involves job assignment, sequencing, and tool management decisions under limited magazine capacities to minimize the makespan. In this paper, we first propose an improved position-based MILP (IPM). This model builds upon the one presented by [1], offering a more compact representation of completion times and is strengthened by static improvement mechanisms inspired by [2]. We then develop a genetic algorithm (GA) using an explicit permutation-assignment encoding and a tool-switch evaluator. Computational experiments were conducted on benchmark instances from the literature. Results show that the IPM solves 58.43% of instances to optimality, outperforming existing formulations, while on medium-size large-scale instances, the proposed GA converges about 50% faster than existing metaheuristic approaches.
Khaled Khayati, K. Salem, Benoit Lardeux et al.· International Conference on...· 0 citations