1,721,140 research outputs found
Comments on: Tabu search tutorial. A Graph Drawing Application
No full textAs suggested by its title, the aim of this paper is to discuss how tabu search can be successfully applied to find high-quality solutions for a wide family of NP-hard optimization problems arising in a huge number of applied mathematics areas. The authors show that a graph drawing problem application is one of those excellent examples, given that since ever geometric representations play an important role in many real-world scenarios and are an important applied branch of graph theory.
This paper is divided in six sections. After an introductory section about the content of the article, a long section follows dedicated to a rich description of the tabu search scheme. The third section describes arc crossing and long arcs issues in graph theory and optimization. In Sect. 4, the authors describe the main ingredients of a tabu search for graph drawing and in Sect. 5 they report an extensive and critical analysis of the computational results they obtained in the comparison of the tabu search they designed with the state of the art techniques. Conclusions are drawn in the last section
An auction-based approach for the re-optimization shortest path tree problem
No full textThe shortest path tree problem is one of the most studied problems in network optimization. Given a directed weighted graph, the aim is to find a shortest path from a given origin node to any other node of the graph. When any change occurs (i.e., the origin node is changed, some nodes/arcs are added/removed to/from the graph, the cost of a subset of arcs is increased/decreased), in order to determine a (still) optimal solution, two different strategies can be followed: a re-optimization algorithm is applied starting from the current optimal solution or a new optimal solution is built from scratch. Generally speaking, the Re-optimization Shortest Path Tree Problem (R-SPTP) consists in solving a sequence of shortest path problems, where the kth problem differs only slightly from the (k- 1) th one, by exploiting the useful information available after each shortest path tree computation. In this paper, we propose an exact algorithm for the R-SPTP, in the case of origin node change. The proposed strategy is based on a dual approach, which adopts a strongly polynomial auction algorithm to extend the solution under construction. The approach is evaluated on a large set of test problems. The computational results underline that it is very promising and outperforms or at least is not worse than the solution approaches reported in the literature
A GRASP for the bus driver scheduling problem
No full textThis paper addresses the problem of determining the best
scheduling for Bus Drivers, i.e. the problem of finding the
minimum number of drivers required to cover a set of
Piece-Of-Works (POWs) subject to a variety of rules and
regulations that must be enforced such as the overspread and the
working time. This problem is known in literature as Crew
Scheduling Problem and in particular in public transportation it
is designated as Bus Driver Scheduling Problem. The Bus Driver
Scheduling Problem is an extremely complex part of the
Transportation Planning System. Its
combinatorial nature and the large dimension of real-world
problems has led to the development of several heuristics. Wren
and Rousseau~\cite{Wren-conference} give an outline of the Bus
Driver Scheduling Problem (BDSP) and propose various approaches for solving it
Shortest path reoptimization vs resolution from scratch: a computational comparison
No full textThe Shortest Path Problem (SPP) is among the most studied problems in Operations Research, for its theoretical aspects but also because it appears as sub-problem in many combinatorial optimization problems, e.g. Vehicle Routing and Maximum Flow-Minimum Cost problems. Given a sequence of SPPs, suppose that two subsequent instances solely differ by a slight change in the graph structure: that is the set of nodes, the set of arcs or both have changed; then, the goal of the reoptimization consists in solving the (Formula presented.) SPP of the sequence by reusing valuable information gathered in the solution of the (Formula presented.) one. We focused on the most general scenario, i.e. multiple changes for any subset of arcs, for which, only the description of a dual-primal approach has been proposed so far [S. Pallottino and M.G. Scutell‘a, A new algorithm for reoptimizing shortest paths when the arc costs change, Oper. Res. Lett. 31 (2003), pp. 149-160.]. We implemented this framework exploiting efficient data structures, i.e. the Multi Level Bucket. In addition, we compare the performance of our proposal with the well-known Dijkstra's algorithm, applied for solving each modified problem from scratch. In this way, we draw the line–in terms of cost, topology, and size–among the instances where the reoptimization approach is efficient from those that should be solved from scratch
Dynamic behaviour of a closed loop driver–car–caravan system
No full textThis work studies the influence of the driver on the dynamic behaviour of a car-caravan system. A plane closed-loop 4-DOF linearised model was developed and the feedback was achieved with a compensation tracking model. The analysis of driver-car interaction was studied through the correlation of different ways of driving and effects on the dynamic response. Moreover, this work shows the influence on the stability of car speed and some design parameters such as the position of the caravan's centroid and cornering stiffness of the axle. The effects on the stability induced by different design choices were verified through the simulation of an obstacle avoidance manoeuvre
Branch and Bound and Dynamic Programming Approaches for the Path Avoiding Forbidden Pairs Problem
No full textWe propose a branch and bound (B&B) and a dynamic programming algorithm for the Path Avoiding Forbidden Pairs Problem (PAFPP). Given a network and a set of forbidden node pairs, the problem consists in finding the shortest path from a source node s to a target node t, avoiding to traverse both nodes of any of the forbidden pairs. The problem has been shown to be NP-complete. In this work, we describe the problem, its mathematical model and we propose two exact algorithms. We compare their performances against those of a commercial solver solving instances for two different graph topologies: fully random graphs and grid graphs
A Bus Driver Scheduling Problem: a new mathematicalmodel and a GRASP approximate solution
No full textThis paper addresses the problem of determining the best scheduling for
Bus Drivers, a N P-hard problem consisting of finding the minimum number of
drivers to cover a set of Pieces-Of-Work (POWs) subject to a variety of rules and
regulations that must be enforced such as spreadover and working time. This problem
is known in literature as Crew Scheduling Problem and, in particular in public
transportation, it is designated as Bus Driver Scheduling Problem. We propose a new
mathematical formulation of a Bus Driver Scheduling Problem under special constraints
imposed by Italian transportation rules. Unfortunately, this model can only
be usefully applied to small or medium size problem instances. For large instances,
a Greedy Randomized Adaptive Search Procedure (GRASP) is proposed. Results
are reported for a set of real-word problems and comparison is made with an exact
method. Moreover, we report a comparison of the computational results obtained
with our GRASP procedure with the results obtained by Huisman et al. (Transp. Sci.
39(4):491–502, 2005)
- …
