Goto

Collaborating Authors

Schönfelder

AAAI Conferences

The functional and the algebraic routing problem are generalizations of the shortest path problem. This paper shows that both problems are equivalent with respect to the concept of profile searches known from time-dependent routing. Because of this, it is possible to apply various shortest path algorithms to these routing problems. This is demonstrated using contraction hierarchies as an example. Furthermore, we show how to use Cousots' concept of abstract interpretation on these routing problems generalizing the idea of routing approximations, which can be used to find approximative solutions and even to improve the performance of exact queries. The focus of this paper lies on vehicle routing while both the functional and algebraic routing models were introduced in the context of internet routing. Due to our formal combination of both fields, new algorithms abound for various specialized vehicle routing problems. We consider two major examples, namely the time-dependent routing problem for public transportation and the energy-efficient routing problem for electric vehicles.


Neural Networks for Dynamic Shortest Path Routing Problems - A Survey

arXiv.org Artificial Intelligence

This paper reviews the overview of the dynamic shortest path routing problem and the various neural networks to solve it. Different shortest path optimization problems can be solved by using various neural networks algorithms. The routing in packet switched multi-hop networks can be described as a classical combinatorial optimization problem i.e. a shortest path routing problem in graphs. The survey shows that the neural networks are the best candidates for the optimization of dynamic shortest path routing problems due to their fastness in computation comparing to other softcomputing and metaheuristics algorithms


UFTR: A Unified Framework for Ticket Routing

arXiv.org Artificial Intelligence

Corporations today face increasing demands for the timely and effective delivery of customer service. This creates the need for a robust and accurate automated solution to what is formally known as the ticket routing problem. This task is to match each unresolved service incident, or "ticket", to the right group of service experts. Existing studies divide the task into two independent subproblems - initial group assignment and inter-group transfer. However, our study addresses both subproblems jointly using an end-to-end modeling approach. We first performed a preliminary analysis of half a million archived tickets to uncover relevant features. Then, we devised the UFTR, a Unified Framework for Ticket Routing using four types of features (derived from tickets, groups, and their interactions). In our experiments, we implemented two ranking models with the UFTR. Our models outperform baselines on three routing metrics. Furthermore, a post-hoc analysis reveals that this superior performance can largely be attributed to the features that capture the associations between ticket assignment and group assignment. In short, our results demonstrate that the UFTR is a superior solution to the ticket routing problem because it takes into account previously unexploited interrelationships between the group assignment and group transfer problems.


A Computational Study of Genetic Crossover Operators for Multi-Objective Vehicle Routing Problem with Soft Time Windows

arXiv.org Artificial Intelligence

The article describes an investigation of the effectiveness of genetic algorithms for multi-objective combinatorial optimization (MOCO) by presenting an application for the vehicle routing problem with soft time windows. The work is motivated by the question, if and how the problem structure influences the effectiveness of different configurations of the genetic algorithm. Computational results are presented for different classes of vehicle routing problems, varying in their coverage with time windows, time window size, distribution and number of customers. The results are compared with a simple, but effective local search approach for multi-objective combinatorial optimization problems.


Sensitive Ants in Solving the Generalized Vehicle Routing Problem

arXiv.org Artificial Intelligence

The idea of sensitivity in ant colony systems has been exploited in hybrid ant-based models with promising results for many combinatorial optimization problems. Heterogeneity is induced in the ant population by endowing individual ants with a certain level of sensitivity to the pheromone trail. The variable pheromone sensitivity within the same population of ants can potentially intensify the search while in the same time inducing diversity for the exploration of the environment. The performance of sensitive ant models is investigated for solving the generalized vehicle routing problem. Numerical results and comparisons are discussed and analysed with a focus on emphasizing any particular aspects and potential benefits related to hybrid ant-based models.