In this paper, we address the electric vehicle routing problem with time windows and propose two branch-and-price-and-cut methods based on a column generation algorithm. One is an exact algorithm whereas the other is ...
详细信息
In this paper, we address the electric vehicle routing problem with time windows and propose two branch-and-price-and-cut methods based on a column generation algorithm. One is an exact algorithm whereas the other is a heuristic method. The pricing sub-problem of the column generation method is solved using a label correcting algorithm. The algorithms are strengthened with the state-of-the-art acceleration techniques and a set of valid inequalities. The acceleration techniques include: (i) an intermediate column pool to prevent solving the pricing sub-problem at each iteration, (ii) a label correcting method employing the ng-route algorithm adopted to our problem, (iii) a bidirectional search mechanism in which both forward and backward labels are created, (iv) a procedure for dynamically eliminating arcs that connect customers to remote stations from the network during the path generation, (v) a bounding procedure providing early elimination of sub-optimal routes, and (vi) an integer programming model that generates upper bounds. Numerical experiments are conducted using a benchmark data set to compare the performances of the algorithms. The results favour the heuristic algorithm in terms of both the computational time and the number of instances solved. Moreover, the heuristic algorithm is shown to be specifically effective for larger instances. Both algorithms introduce a number of new solutions to the literature.
This paper describes how drivers' rules according to EU social legislation can be formally modelled using the resource concept and how 'legal' vehicle routes and schedules can be computed by exact and heur...
详细信息
The Argumentation Frameworks with Necessities (AFNs) proposed in [17] are a kind of bipolar AFs extending Dung AFs with a support relation having the particular meaning of necessity. This paper is a continuation of th...
详细信息
ISBN:
(纸本)9783642403811;9783642403804
The Argumentation Frameworks with Necessities (AFNs) proposed in [17] are a kind of bipolar AFs extending Dung AFs with a support relation having the particular meaning of necessity. This paper is a continuation of this work in two respects. First, we complete the acceptability semantics picture by defining the well-founded, the complete and the semi-stable semantics for AFNs. We show that the proposed semantics keep the same properties as those given for Dung AFs and represent proper generalizations of them (in absence of the necessity relation, the classical semantics are recovered). Then, we show how to generalize Caminada's labelling algorithms in presence of a necessity relation to compute the extensions under the studied semantics for AFNs.
For the BMBF founded project of Road-Traffic Image Observation (BMBF 03WK J02B) the DLR- Institute for optical information system developed an optical based observation system for the control of roads and traffic, rea...
详细信息
ISBN:
(纸本)9806560477
For the BMBF founded project of Road-Traffic Image Observation (BMBF 03WK J02B) the DLR- Institute for optical information system developed an optical based observation system for the control of roads and traffic, realized by computer vision approaches. Efficient algorithms for robust and fast image processing extract objects, like motor vehicles and non-motorized traffic. The computation algorithms have to be robust for day and night, They have to process the image data in real-time from the observation traffic junctions. Some of theses special algorithms are also suitable for a similar new project for airport monitoring and surveillance, with the goal in the detection of movements of planes.
暂无评论