CS Paper Radar

Node-Shift-Encoding Genetic Algorithm with fuzzy-enhanced reference tour to solve the bi-objective service-oriented TSP

Souad Abdoune, Menouar Boulif

cs.CE ·submitted 2026-09-10 08:53 UTC · v1

Abstract

The Travelling Salesman Problem (TSP) remains a key area of research in combinatorial optimization, with applications in logistics, manufacturing, and service delivery. This paper addresses a bi-objective service-oriented TSP in which the clients' ranks in the delivery path matter. Unlike conventional depot-based TSP formulations, the considered problem does not assume a distinguished depot or a fixed tour origin. To address this setting, we adapt the Miller--Tucker--Zemlin (MTZ)-based formulation and derive an original linearization of the resulting model, enabling its solution with off-the-shelf integer linear programming solvers. This adaptation avoids the rigid tour origin imposed by the conventional MTZ formulation, for which fixing the starting node does not affect the tour cost but can affect the objective in a customer-rank-sensitive TSP. To solve this problem, we present a Node-Shift-Encoding (NSE)-based Genetic Algorithm augmented with fuzzy reasoning to update the reference tour throughout the evolutionary process. Experimental evaluation on TSPLIB benchmarks demonstrates that the proposed method achieves improved performance compared with the classical NSE approach.

Comment
22 pages, 13 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Evolutionary Giant Tour for CVRP using NSE and ML Heuristic]{Evolutionary Giant Tour approach for CVRP using Node Shift Encoding and Machine Learning repair heuristic

cs.NE ·2026-10-01 ·Souad Abdoune, Menouar Boulif
benchmark similarity 0.65
Abstract · 21 pages, 16 figures

The Capacitated Vehicle Routing Problem (CVRP) remains a central concern in logistics research, as route optimisation under rigid capacity and fleet restrictions directly affects operational performance. Genetic Algorithms are widely used for this problem, yet their effectiveness depends heavily on the choice of solution encoding and on the mechanisms used to preserve feasibility during the search. This paper proposes a sequential framework that separates the evolutionary process from route construction. We adapt Node Shift Encoding (NSE) to the CVRP giant-tour setting and benchmark it against Path Representation and Double Chromosome. We further propose an unsupervised machine-learning repair heuristic that restores fleet feasibility after an unconstrained linear split, and compare this pipeline against fleet-constrained split taken from the literature. Computational tests on standard benchmark instances show that NSE consistently outperforms the other encodings in solution quality and feasibility. The repair heuristic restores feasibility in approximately 72\% of cases, and the Linear-Split-ML-Heuristic pipeline proves more robust than the constrained split, delivering lower costs and higher feasibility rates.

0.28

A Graph Neural Network--Guided Genetic Algorithm for Physical Internet Supply Chain Optimization under Cost Uncertainty

cs.NE cs.LG ·2026-08-10 ·Faezeh Ardali, Gerald M. Knapp
published similarity 0.59
Abstract · 6 pages

Inventory and distribution planning in Physical Internet networks requires coordinating factory-hub assignments, factory supply, lateral transshipment among collaborative hubs, retailer deliveries, and shortages. The problem combines discrete assignment decisions with interdependent continuous flows, while uncertain operating costs make robust planning more difficult. This study formulates deterministic and min-max regret models for a three-echelon network of factories, hubs, and retailers and develops a graph neural network-guided genetic algorithm (GNN-GA) for the assignment decisions. The GNN estimates hub-specific factory-selection probabilities that are used to construct the initial GA population and adapt mutation according to prediction uncertainty. Each previously unseen candidate assignment is evaluated by solving the remaining continuous-flow problem to LP optimality. Simulated annealing, a standard GA, and GNN-GA are compared on 15 instances using matched random seeds and fixed limits on distinct assignment evaluations. Because the evaluation budgets for test Instances 13-15 are smaller than the nominal population size, these experiments primarily assess the quality of learned initialization rather than multi-generation evolutionary search. A separate 400-evaluation experiment on exact test Instance 13 permits three complete offspring generations and a partial fourth pass, with GNN-GA outperforming GA in all 10 matched runs. Three independently generated exact-solvable instances provide a separate test of transfer. Ablation results show that learned initialization provides most of the improvement, while entropy-guided mutation has a smaller, instance-dependent effect. Per-instance solution times include GNN inference and search but exclude model training and one-time model setup.

0.24

The Time-Dependent Traveling Salesman Problem with Loose Time Windows

cs.DS ·2026-08-26 ·Francisco J. Soulignac
benchmark similarity 0.57
Abstract · 24 pages, 2 figures

The time-dependent traveling salesman problem with time windows (TDTSPTW) generalizes the well-known traveling salesman problem with time windows by accounting the effects of congestion on travel times. In this paper, we develop an exact framework for the TDTSPTW with a makespan objective that extends the range of instances solvable to optimality under loose time windows while remaining effective across all levels of time-window tightness. Our framework relies on a dynamic-programming labeling algorithm and combines column generation, ng-memory augmentation, and exact search, using completion bounds for state-space sparsification, variable fixing, and exact search pruning. Embedded within a branch-and-price method, the framework solves all instances with up to 45 customers in a benchmark comprising more than 10,000 instances, including all instances without time windows with up to 50 customers.

0.29

Tailoring Optimization Approaches with Domain Knowledge in Industry Process for Meta-heuristic Development

cs.NE cs.AI ·2026-11-10 ·Jakub Cebula, Konrad Gmyrek, Paweł B. Myszkowski, Marko Đurasević, Łukasz P. Olech +1 more
similarity 0.57
Abstract

The paper presents an Industry Process for Meta-heuristic Development (IPMD) schema, a systematic methodology for applying meta- and hyper-heuristic applications to optimization problems. In this context, we present a case study of Balancing Non-dominated Tournament Genetic Programming (BNTGP) applied to solve two NP-hard multi-objective optimization problems: routing (Capacitated Vehicle Routing Problem with Time Windows) and scheduling (Multi-Skill Resource Constrained Project Scheduling Problem). The BNTGP method is based on a metaheuristic design. Its genetic programming-based representation makes BNTGP a hyper-heuristic, as it enables the exploration of a search space of heuristics for solving problems in general. The resulting heuristic can then be applied across a set of problem instances.

0.21

Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

cs.AI cs.LO ·2026-08-11 ·Alessandro Bertagnon, Marco Gavanelli
published similarity 0.57
Abstract · Accepted for publication in Theory and Practice of Logic Programming (TPLP), 36 pages, 14 figures

The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications, such as smart vehicles and intelligent transportation systems. In the "Euclidean" case, each node is defined by its coordinates in the plane and distances are computed using the Euclidean metric. In the Constraint Programming (CP) literature, the Euclidean TSP is typically addressed by computing the full distance matrix and treating it as a general case; however this approach ignores the geometric information carried by the points' coordinates. In this work, we propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches. Moreover, we show how this methodology can be extended to other Euclidean variants of the TSP, including the Euclidean Generalized Traveling Salesperson Problem (EGTSP), which is relevant in practical routing and logistics applications. Experimental results demonstrate the computational advantages of the proposed approach.

0.29

LLM-Driven Joint Evolution of Coupled Heuristics Components for Routing Optimization

cs.NE ·2026-09-02 ·Juntao Wei, Yangming Zhou, Zhibin Jiang, Shan Jiang
similarity 0.56
Abstract

Heuristic design for combinatorial optimization remains heavily reliant on expert knowledge, while existing large language model (LLM)-enhanced evolutionary methods typically evolve isolated algorithmic components, even when one determines the search state on which another operates. This paper proposes LLM-driven Heuristic Components Joint Generation (LLM-HCJG), a population-based framework that jointly generates and co-evolves interdependent heuristic components under a shared design blueprint. Applied to guided local search (GLS), LLM-HCJG couples solution initialization with penalty construction and embeds the generated pair into an enhanced online search mechanism. The resulting form is further transferred from the traveling salesman problem (TSP) to the capacitated vehicle routing problem (CVRP). Theoretical analysis establishes the non-separable state-transition effects between the two components and the advantage in generation consistency. Across synthetic instances and 41 public TSPLIB/CVRPLIB benchmarks, LLM-HCJG attains consistently low optimality gaps, including best or tied-best results on 28 of 29 TSPLIB instances and all 12 CVRPLIB instances. Ablation and structural analyses further indicate that these gains are associated with cross-component compatibility and alignment rather than isolated-component recombination. These results support effective cross-instance transfer within the evaluated routing settings under limited-sample, modest-cost training.

0.31

Joint pricing and matching for dynamic high-capacity ride-sharing considering passengers' choice uncertainty

eess.SY ·2026-08-23 ·Wang Chen, Xinglu Liu, Kaihang Zhang, Hongzheng Shi, Jintao Ke
similarity 0.56
Abstract

This work investigates the uncertainty-aware joint pricing and matching problem for dynamic high-capacity ride-sharing services, where passengers are assumed to be price-elastic and decide whether to accept a ride-sharing offer based on the upfront prices provided by the platform. We formulate the studied problem as a two-stage stochastic program, where the first stage optimizes upfront price decisions for passengers, and the second-stage recourse problem captures passenger-vehicle assignment based on passengers' uncertain choices. To enhance computational efficiency, we introduce a novel relaxation-based gradient descent-guided search algorithm that leverages the problem's structural properties. Initially, the algorithm generates a feasible solution for the first-stage problem via relaxation. It then iteratively improves the solution via a search process guided by the derived gradient information. In particular, scenario reduction is applied to eliminate unnecessary scenarios when calculating the gradient, thereby reducing the overall computational burden. Numerical experiments demonstrate that, compared to solving the stochastic program directly, the proposed algorithm can accelerate computation speed by thousands of times while achieving optimality gaps of no more than 1.1%. Finally, we validate the benefits of considering passengers' choice uncertainty through large-scale simulation using real-world datasets and road networks over two large cities. The results demonstrate that, on average, the proposed method can increase the revenue by 5.2% and the service rate by 8.2% compared to the baseline approaches. This study provides a valuable reference for transportation network companies to design pricing strategies for ride-sharing to enhance service efficiency and improve revenue.

0.34

A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem

cs.AI ·2026-11-17 ·The Dung Bui, Ha Thu Nguyen
code/data similarity 0.55
Abstract · 5 pages, 1 figure, 2 tables. Technical Report for the SOICT 2026 Student Contest. Code: https://github.com/25023189-bit/Integrated-Passenger…

We describe the solver we submitted to the second round of the SOICT 2026 contest on the Integrated Passenger and Parcel Transportation problem, a selective pickup-and-delivery routing problem with time windows, open routes and heterogeneous taxis. The solver is a single-file, standard-library Python program that combines (i) a constant-time insertion test based on latest-arrival slack, (ii) greedy insertion, local search and an Adaptive Large Neighborhood Search (ALNS) with simulated-annealing acceptance, and (iii) an exact route-selection engine that enumerates, for every taxi, the best feasible route for each request set and then solves the resulting set-packing problem by branch-and-bound strengthened with route-based large neighborhood search, Lagrangian bounds and reduced-cost fixing. The engine is chosen automatically from the instance size, and an independent verifier and a watchdog guarantee that a valid answer is always printed. On the official evaluation (38 scored instances, 5-minute limit) the solver obtained a total benefit of 487,237, finished every run within 277 s and used at most 279 MB; 28 of the 38 instances terminated well before the limit.

0.34