Relevant bibliographies by topics / Uncertain Capacitated Arc Routing Problem

Academic literature on the topic 'Uncertain Capacitated Arc Routing Problem'

Author: Grafiati
Published: 10 December 2022
Last updated: 29 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Uncertain Capacitated Arc Routing Problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Uncertain Capacitated Arc Routing Problem"

1

MacLachlan, Jordan, Yi Mei, Juergen Branke, and Mengjie Zhang. "Genetic Programming Hyper-Heuristics with Vehicle Collaboration for Uncertain Capacitated Arc Routing Problems." Evolutionary Computation 28, no. 4 (December 2020): 563–93. http://dx.doi.org/10.1162/evco_a_00267.

Full text
Abstract:
Due to its direct relevance to post-disaster operations, meter reading and civil refuse collection, the Uncertain Capacitated Arc Routing Problem (UCARP) is an important optimisation problem. Stochastic models are critical to study as they more accurately represent the real world than their deterministic counterparts. Although there have been extensive studies in solving routing problems under uncertainty, very few have considered UCARP, and none consider collaboration between vehicles to handle the negative effects of uncertainty. This article proposes a novel Solution Construction Procedure (SCP) that generates solutions to UCARP within a collaborative, multi-vehicle framework. It consists of two types of collaborative activities: one when a vehicle unexpectedly expends capacity ( route failure), and the other during the refill process. Then, we propose a Genetic Programming Hyper-Heuristic (GPHH) algorithm to evolve the routing policy used within the collaborative framework. The experimental studies show that the new heuristic with vehicle collaboration and GP-evolved routing policy significantly outperforms the compared state-of-the-art algorithms on commonly studied test problems. This is shown to be especially true on instances with larger numbers of tasks and vehicles. This clearly shows the advantage of vehicle collaboration in handling the uncertain environment, and the effectiveness of the newly proposed algorithm.
APA, Harvard, Vancouver, ISO, and other styles
2

Liu, Yuxin, Yi Mei, Mengjie Zhang, and Zili Zhang. "A Predictive-Reactive Approach with Genetic Programming and Cooperative Coevolution for the Uncertain Capacitated Arc Routing Problem." Evolutionary Computation 28, no. 2 (June 2020): 289–316. http://dx.doi.org/10.1162/evco_a_00256.

Full text
Abstract:
The uncertain capacitated arc routing problem is of great significance for its wide applications in the real world. In the uncertain capacitated arc routing problem, variables such as task demands and travel costs are realised in real time. This may cause the predefined solution to become ineffective and/or infeasible. There are two main challenges in solving this problem. One is to obtain a high-quality and robust baseline task sequence, and the other is to design an effective recourse policy to adjust the baseline task sequence when it becomes infeasible and/or ineffective during the execution. Existing studies typically only tackle one challenge (the other being addressed using a naive strategy). No existing work optimises the baseline task sequence and recourse policy simultaneously. To fill this gap, we propose a novel proactive-reactive approach, which represents a solution as a baseline task sequence and a recourse policy. The two components are optimised under a cooperative coevolution framework, in which the baseline task sequence is evolved by an estimation of distribution algorithm, and the recourse policy is evolved by genetic programming. The experimental results show that the proposed algorithm, called Solution-Policy Coevolver, significantly outperforms the state-of-the-art algorithms to the uncertain capacitated arc routing problem for the ugdb and uval benchmark instances. Through further analysis, we discovered that route failure is not always detrimental. Instead, in certain cases (e.g., when the vehicle is on the way back to the depot) allowing route failure can lead to better solutions.
APA, Harvard, Vancouver, ISO, and other styles
3

Liu, Jialin, Ke Tang, and Xin Yao. "Robust Optimization in Uncertain Capacitated Arc Routing Problems: Progresses and Perspectives [Review Article]." IEEE Computational Intelligence Magazine 16, no. 1 (February 2021): 63–82. http://dx.doi.org/10.1109/mci.2020.3039069.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Wang, Juan, Ke Tang, Jose A. Lozano, and Xin Yao. "Estimation of the Distribution Algorithm With a Stochastic Local Search for Uncertain Capacitated Arc Routing Problems." IEEE Transactions on Evolutionary Computation 20, no. 1 (February 2016): 96–109. http://dx.doi.org/10.1109/tevc.2015.2428616.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Babaee Tirkolaee, Erfan, Iraj Mahdavi, Mir Mehdi Seyyed Esfahani, and Gerhard-Wilhelm Weber. "A hybrid augmented ant colony optimization for the multi-trip capacitated arc routing problem under fuzzy demands for urban solid waste management." Waste Management & Research 38, no. 2 (August 13, 2019): 156–72. http://dx.doi.org/10.1177/0734242x19865782.

Full text
Abstract:
Nowadays, urban solid waste management is one of the most crucial activities in municipalities and their affiliated organizations. It includes the processes of collection, transportation and disposal. These major operations require a large amount of resources and investments, which will always be subject to limitations. In this paper, a chance-constrained programming model based on fuzzy credibility theory is proposed for the multi-trip capacitated arc routing problem to cope with the uncertain nature of waste amount generated in urban areas with the aim of total cost minimization. To deal with the complexity of the problem and solve it efficiently, a hybrid augmented ant colony optimization algorithm is developed based on an improved max–min ant system with an innovative probability function and a simulated annealing algorithm. The performance of hybrid augmented ant colony optimization is enhanced by using the Taguchi parameter design method to adjust the parameters’ values optimally. The overall efficiency of the algorithm is evaluated against other similar algorithms using well-known benchmarks. Finally, the applicability of the suggested methodology is tested on a real case study with a sensitivity analysis to evolve the managerial insights and decision aids.
APA, Harvard, Vancouver, ISO, and other styles
6

Babaee Tirkolaee, Erfan, Alireza Goli, Maryam Pahlevan, and Ramina Malekalipour Kordestanizadeh. "A robust bi-objective multi-trip periodic capacitated arc routing problem for urban waste collection using a multi-objective invasive weed optimization." Waste Management & Research 37, no. 11 (August 15, 2019): 1089–101. http://dx.doi.org/10.1177/0734242x19865340.

Full text
Abstract:
Urban waste collection is one of the principal processes in municipalities with large expenses and laborious operations. Among the important issues raised in this regard, the lack of awareness of the exact amount of generated waste makes difficulties in the processes of collection, transportation and disposal. To this end, investigating the waste collection issue under uncertainty can play a key role in the decision-making process of managers. This paper addresses a novel robust bi-objective multi-trip periodic capacitated arc routing problem under demand uncertainty to treat the urban waste collection problem. The objectives are to minimize the total cost (i.e. traversing and vehicles’ usage costs) and minimize the longest tour distance of vehicles (makespan). To validate the proposed bi-objective robust model, the ε-constraint method is implemented using the CPLEX solver of GAMS software. Furthermore, a multi-objective invasive weed optimization algorithm is then developed to solve the problem in real-world sizes. The parameters of the multi-objective invasive weed optimization are tuned optimally using the Taguchi design method to enhance its performance. The computational results conducted on different test problems demonstrate that the proposed algorithm can generate high-quality solutions considering three indexes of mean of ideal distance, number of solutions and central processing unit time. It is proved that the ε-constraint method and multi-objective invasive weed optimization can efficiently solve the small- and large-sized problems, respectively. Finally, a sensitivity analysis is performed on one of the main parameters of the problem to study the behavior of the objective functions and provide the optimal policy.
APA, Harvard, Vancouver, ISO, and other styles
7

Usberti, Fábio Luiz, Paulo Morelato França, and André Luiz Morelato França. "The open capacitated arc routing problem." Computers & Operations Research 38, no. 11 (November 2011): 1543–55. http://dx.doi.org/10.1016/j.cor.2011.01.012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Kirlik, Gokhan, and Aydin Sipahioglu. "Capacitated arc routing problem with deadheading demands." Computers & Operations Research 39, no. 10 (October 2012): 2380–94. http://dx.doi.org/10.1016/j.cor.2011.12.008.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Benavent, E., V. Campos, A. Corberan, and E. Mota. "The Capacitated Arc Routing Problem: Lower bounds." Networks 22, no. 7 (December 1992): 669–90. http://dx.doi.org/10.1002/net.3230220706.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Amaya, Alberto, André Langevin, and Martin Trépanier. "The capacitated arc routing problem with refill points." Operations Research Letters 35, no. 1 (January 2007): 45–53. http://dx.doi.org/10.1016/j.orl.2005.12.009.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Uncertain Capacitated Arc Routing Problem"

1

Helal, Nathalie. "An evidential answer for the capacitated vehicle routing problem with uncertain demands." Thesis, Artois, 2017. http://www.theses.fr/2017ARTO0208/document.

Full text
Abstract:
Le problème de tournées de véhicules avec contrainte de capacité est un problème important en optimisation combinatoire. L'objectif du problème est de déterminer l'ensemble des routes, nécessaire pour servir les demandes déterministes des clients ayant un cout minimal, tout en respectant la capacité limite des véhicules. Cependant, dans de nombreuses applications réelles, nous sommes confrontés à des incertitudes sur les demandes des clients. La plupart des travaux qui ont traité ce problème ont supposé que les demandes des clients étaient des variables aléatoires. Nous nous proposons dans cette thèse de représenter l'incertitude sur les demandes des clients dans le cadre de la théorie de l'évidence - un formalisme alternatif pour modéliser les incertitudes. Pour résoudre le problème d'optimisation qui résulte, nous généralisons les approches de modélisation classiques en programmation stochastique. Précisément, nous proposons deux modèles pour ce problème. Le premier modèle, est une extension de l'approche chance-constrained programming, qui impose des bornes minimales pour la croyance et la plausibilité que la somme des demandes sur chaque route respecte la capacité des véhicules. Le deuxième modèle étend l'approche stochastic programming with recourse: l'incertitude sur les recours (actions correctives) possibles sur chaque route est représentée par une fonction de croyance et le coût d'une route est alors son coût classique (sans recours) additionné du pire coût espéré des recours. Certaines propriétés de ces deux modèles sont étudiées. Un algorithme de recuit simulé est adapté pour résoudre les deux modèles et est testé expérimentalement
The capacitated vehicle routing problem is an important combinatorial optimisation problem. Its objective is to find a set of routes of minimum cost, such that a fleet of vehicles initially located at a depot service the deterministic demands of a set of customers, while respecting capacity limits of the vehicles. Still, in many real-life applications, we are faced with uncertainty on customer demands. Most of the research papers that handled this situation, assumed that customer demands are random variables. In this thesis, we propose to represent uncertainty on customer demands using evidence theory - an alternative uncertainty theory. To tackle the resulting optimisation problem, we extend classical stochastic programming modelling approaches. Specifically, we propose two models for this problem. The first model is an extension of the chance-constrained programming approach, which imposes certain minimum bounds on the belief and plausibility that the sum of the demands on each route respects the vehicle capacity. The second model extends the stochastic programming with recourse approach: it represents by a belief function for each route the uncertainty on its recourses (corrective actions) and defines the cost of a route as its classical cost (without recourse) plus the worst expected cost of its recourses. Some properties of these two models are studied. A simulated annealing algorithm is adapted to solve both models and is experimentally tested
APA, Harvard, Vancouver, ISO, and other styles
2

Bode, Claudia [Verfasser], and Stefan [Verfasser] Irnich. "Cut-first branch-and-price-second for the capacitated arc-routing problem / Claudia Bode, Stefan Irnich." Mainz : Universitätsbibliothek der Johannes Gutenberg-Universität Mainz, 2011. http://d-nb.info/1225558654/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bernardo, Papini Marcella Verfasser], Pannek [Akademischer Betreuer] Pannek, Pannek [Gutachter] Pannek, and Hans-Dietrich [Gutachter] [Haasis. "Robust Capacitated Vehicle Routing Problem with Uncertain Demands / Marcella Bernardo Papini ; Gutachter: Pannek Pannek, Hans-Dietrich Haasis ; Betreuer: Pannek Pannek." Bremen : Staats- und Universitätsbibliothek Bremen, 2019. http://d-nb.info/1196286310/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Usberti, Fábio Luiz 1982. "Métodos heurísticos e exatos para o problemas de roteamento em arcos capacitado e aberto = Heuristic and exact approaches for the open capacitated arc routing problem." [s.n.], 2012. http://repositorio.unicamp.br/jspui/handle/REPOSIP/260624.

Full text
Abstract:
Orientadores: André Luiz Morelato França, Paulo Morelato França
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação
Made available in DSpace on 2018-08-20T08:47:23Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_D.pdf: 2207082 bytes, checksum: 83078a448a40f75c373b989f9af006fb (MD5) Previous issue date: 2012
Resumo:O problema de roteamento em arcos capacitado e aberto (open capacitated arc routing problem, OCARP) é um problema de otimização combinatorial NP-difícil em que, dado um grafo não-direcionado, o objetivo consiste em encontrar um conjunto de rotas de custo mínimo para veículos com capacidade restrita que atendam a demanda de um subconjunto de arestas. O OCARP está relacionado com o problema de roteamento em arcos capacitado (capacitated arc routing problem, CARP), mas difere deste pois o OCARP não possui um nó depósito e as rotas não estão restritas a ciclos. Aplicações da literatura para o OCARP são discutidas. Uma formula ção de programação linear inteira é fornecida junto com propriedades do problema. Uma metaheurística GRASP (greedy randomized adaptive search procedure) com reconexão por caminhos (path-relinking) é proposta e comparada com outras metaheurísticas bem-sucedidas da literatura. Algumas características do GRASP são: (i) ajuste reativo de parâmetros, cujos valores são estocasticamente selecionados com viés 'aqueles valores que produziram, em média, as melhores soluções; (ii) um filtro estatístico que descarta soluções iniciais caso estas tenham baixa probabilidade de superar a melhor solução incumbente; (iii) uma busca local infactível que gera soluções de baixo custo utilizadas para explorar fronteiras factíveis/infactíveis do espaço de soluções; (iv) a reconexão por caminhos evolutiva aprimora progressivamente um conjunto de soluções de elevada qualidade (soluções elites). Testes computacionais foram conduzidos com instâncias CARP e OCARP e os resultados mostram que o GRASP é bastante competitivo, atingindo os melhores desvios entre os custos das soluções e limitantes inferiores conhecidos. Este trabalho também propõe um algoritmo exato para o OCARP que se baseia no paradigma branch-and-bound. Três limitantes inferiores são propostos e um deles utiliza o método dos subgradientes para resolver uma relaxação lagrangeana. Testes computacionais comparam o algoritmo branch-and-bound com o CPLEX resolvendo um modelo reduzido OCARP de programa ção linear inteira. Os resultados revelam que o algoritmo branch-and-bound apresentou resultados melhores que o CPLEX no que diz respeito aos desvios entre limitantes e ao número de melhores soluções
Abstract: The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. An integer linear programming formulation is given, followed by some properties of the problem. A Greedy Randomized Adaptive Search Procedure (GRASP) with path-relinking (PR) solution method is proposed and compared with other successful metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the metaheuristic parameters values are stochastically selected biased in favor of those values which produced the best solutions in average; (ii) a statistical filter, which discards initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend in which a pool of elite solutions is progressively improved by relinking pairs of elite solutions. Computational tests were conducted for both CARP and OCARP instances, and results reveal that the GRASP with PR is very competitive, achieving the best overall deviation from lower bounds. This work also proposes an exact algorithm for OCARP, based on the branch-and-bound paradigm. Three lower bounds are proposed, one of them uses a subgradient method to solve a Lagrangian relaxation. The computational tests compared the proposed branch-and-bound with a commercial state-of-the-art ILP solver. Results reveal that the branch-and-bound outperformed CPLEX in the overall average deviation from lower bounds
Doutorado
Automação
Doutor em Engenharia Elétrica
APA, Harvard, Vancouver, ISO, and other styles
5

Franc, Zdeněk. "Kapacitní problém listonoše." Master's thesis, Vysoká škola ekonomická v Praze, 2014. http://www.nusl.cz/ntk/nusl-193813.

Full text
Abstract:
The Capacitated Arc Routing Problem has many applications in real life. The aim of this problem is to minimize the total cost at fulfilment of the requirements of arcs. The Capacitated Arc Routing Problem is an extension of the Chinese Postman Problem, which is a special type of the Vehicle Routing Problems. In this thesis is explained the issue of the Chinese Postman Problem and its extensions at first. Subsequently the applications of mathematical models are illustrated on a model example. However these mathematical models, which are searching the optimal solution, do not use so much in reality. Therefore the randomized heuristic algorithm for solving these problems is suggested and programmed in this thesis. Subsequently this heuristic was applied to case study of garbage collection in Podebrady city.
APA, Harvard, Vancouver, ISO, and other styles
6

Nunes, Ana Catarina de Carvalho. "Sectorização de redes em problemas com procura nos arcos e limitações de capacidade." Doctoral thesis, Instituto Superior de Economia e Gestão, 2009. http://hdl.handle.net/10400.5/1252.

Full text
Abstract:
Doutoramento em Matemática Aplicada à Economia e à Gestão
O problema de sectorização e rotas nos arcos (SARP) e definido para modelar as actividades associadas as ruas de zonas urbanas, como sendo o caso da recolha municipal de resíduos sólidos. Com o SARP pretende obter-se uma partição da rede de ruas em sectores e construir um conjunto de viagens em cada sector, minimizando a duração total das viagens. São apresentadas formulações para o SARP, conhecidas por formulações de fluxos por utilizarem variáveis de fluxo. Estas formulações tem a vantagem de impedir a formação de viagens ilegais usando um número polinomial de restrições, em alternativa as habituais restrições de eliminação de subcircuitos, que são em número exponencial. Com base nestas formulações são determinados limites inferiores para o valor óptimo do SARP e, para instancias de baixa dimensão, são obtidas soluções óptimas. São propostas duas heurísticas em duas fases e uma heurística de melhor inserção, com várias versões cada. Nas heurísticas em duas fases, na fase 1 constroem-se os sectores usando duas heurísticas possíveis, enquanto que na fase 2 e resolvido um problema de rotas com procura nos arcos e restrições de capacidade num grafo misto (MCARP) para determinar as viagens em cada sector. A heurística de melhor inserção determina os sectores e as viagens em simultâneo. Para alem do custo da solução, os algoritmos são comparados usando outros critérios de avaliação, tais como o desequilíbrio, o diâmetro e medidas da dispersão. São mostrados e analisados os resultados obtidos para três conjuntos de instâncias, incluindo instâncias de grandes dimensões com ate 401 nodos e 1056 ligacões (arcos ou arestas).
The Sectoring-Arc Routing Problem (SARP) is introduced to model activities associated with the streets of large urban areas, like municipal waste collection. The aim is to partition the street network into a given number of sectors and to build a set of vehicle trips in each sector, to minimize the total duration of the trips. SARP formulations using flow variables, known as flow formulations, are given. One of the advantages of this type of formulation is that it involves a polynomial number of constraints to eliminate illegal trips, instead of the usual subtour elimination constraints, which are in exponential number. From these formulations lower bounds for the SARP are derived and, for small instances, optimal solutions are obtained. Two two-phase heuristics and one best insertion method are proposed. In the two-phase methods, phase 1 constructs the sectors using two possible heuristics, while phase 2 solves a Mixed Capacitated Arc Routing Problem (MCARP) to compute the trips in each sector. The best insertion method determines sectors and trips simultaneously. In addition to solution cost, some evaluation criteria such as imbalance, diameter and dispersion measures are used to compare algorithms. Numerical results on large instances with up to 401 nodes and 1056 links (arcs or edges) are reported and analysed.
APA, Harvard, Vancouver, ISO, and other styles
7

Al-Hasani, Firas Ali Jawad. "Multiple Constant Multiplication Optimization Using Common Subexpression Elimination and Redundant Numbers." Thesis, University of Canterbury. Electrical and Computer Engineering, 2014. http://hdl.handle.net/10092/9054.

Full text
Abstract:
The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations. A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity. A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.
APA, Harvard, Vancouver, ISO, and other styles
8

Su, Chia-Nan, and 蘇家男. "The Study of Lower Bound of Capacitated Arc Routing Problem." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/37183606308000649687.

Full text
Abstract:
碩士
國立交通大學
運輸工程與管理系
87
The Capacitated Arc Routing Problem (CARP) is a commonly seen problem in logistic. CARP finds a set of routes that serve each service edge exactly once while satisfying the capacity constraint.CARP was proved to be a NP-Hard problem. Thus, is difficult to find the optimal solution with a reasonable amount of time. Thus, the study focuses in finding a good lower bound which can be used to speed up the B-B process This paper introduces two lower bounds of CARP:1.the Arc Scanning Lower Bound (ASLB). In steady of considering nodes as most reaches do, ASLB use edge to compute the lower bound. We also prove our ASLB is no worse than the performance of NSLB. 2.the Hybrid Lower Bound (HLB). We also propose a HLB method to find the Lower Bound. This method use the idea From Benavent(1992) and Yasufumi(1992). We observe that HLB perform better who the demand of some edges exceed half of the vehicle capacity and the costs of edges differ significantly.
APA, Harvard, Vancouver, ISO, and other styles
9

Lu, Li-Chun, and 呂理鈞. "An Iterated Local Search for the Periodic Capacitated Arc Routing Problem." Thesis, 2018. http://ndltd.ncl.edu.tw/handle/2h62zk.

Full text
Abstract:
碩士
元智大學
工業工程與管理學系
106
The Periodic Capacitated Arc Routing Problem (PCARP) is a challenging topic with many important applications, such as snow plowing, street sweeping, winter gritting and waste collection. PCARP is an extension of the well-known Capacitated Arc Routing Problem (CARP) which planned over a multi-period horizontal. The objective is to minimize the total distance of the trips on the entire planning horizon to serve the required arcs. The first step is to assign the required arcs to each day by the date combination, and then solve the resulting CARP for each day. Because the PCARP is an NP-hard problem, we propose an effective Iterated Local Search (ILS) to solve it. The result is improved by the Randomized Variable Neighborhood Descent (RVND) which is combined by different kinds of local search. RVND is an efficient way to find more possibilities of results. The proposed ILS is tested on eight sets of classical CARP benchmarks and three sets of PCARP benchmark instances from the literature, and compared with the other algorithms. The computational result shows that ILS is effective to solve the CARP and reaches 80% of best known solutions in all instances. On the other hand, ILS has a good performance in solving PCARP as well. It indicates that ILS is applicable to CARP and PCARP. In the practical application, we applies the ILS to solve the real street washing planning problem in Taipei City. The result shows that the travel distance of street washing planning problem can be reduced by arranging and planning the new routes with our ILS algorithm. In the future, we hope that this research can contribute to public planning.
APA, Harvard, Vancouver, ISO, and other styles
10

Tsai, Han-Shiuan, and 蔡函軒. "The Capacitated Arc Routing Problem and Its Application in Street Cleaning Planning." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/60605495043603213545.

Full text
Abstract:
碩士
元智大學
工業工程與管理學系
104
The capacitated arc routing problem (CARP) is a special routing problem which has a variety of practical applications, such as snow plowing, street sweeping, winter gritting, household waste collection, The classical CARP is defined on an undirected graph with a set of edges. Each edge has a routing cost and a demand. The edges with positive demand make up the subset of the required edges. A set of identical vehicles with limited capacity is available. Each required edge has to be served exactly once by one vehicle. Each route must start and end at the depot. The objective of CARP is to find a set of vehicle routes to minimize the total cost. Due to that CARP is a NP-hard problem, this research intends to present an Ant Colony Optimization (ACO) meta-heuristic to solve the CARP. The result is further improved by a local search with path-relinking for ACO. ACO is tested on eight groups of benchmark instances from the literature. The computational results show that ACO is effective to solve the CARP and its performance is highly competitive. ACO reaches 90% best known solutions in all instances. In the practical application, this research applies the proposed ACO to solve the street cleaning planning problem with intermediate refill points in Kaohsiung city. The results are presented in a road network on the Google Map. The results show that the travel distance of street cleaning can be reduced by arranging and planning the new routes under our ACO algorithm. Finally, we hope that this research will add time windows and fuel costs constraints in the future.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Uncertain Capacitated Arc Routing Problem"

1

MacLachlan, Jordan, Yi Mei, Juergen Branke, and Mengjie Zhang. "An Improved Genetic Programming Hyper-Heuristic for the Uncertain Capacitated Arc Routing Problem." In AI 2018: Advances in Artificial Intelligence, 432–44. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-03991-2_40.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ansari Ardeh, Mazhar, Yi Mei, and Mengjie Zhang. "A Novel Genetic Programming Algorithm with Knowledge Transfer for Uncertain Capacitated Arc Routing Problem." In PRICAI 2019: Trends in Artificial Intelligence, 196–200. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-29908-8_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Ardeh, Mazhar Ansari, Yi Mei, and Mengjie Zhang. "A Parametric Framework for Genetic Programming with Transfer Learning for Uncertain Capacitated Arc Routing Problem." In AI 2020: Advances in Artificial Intelligence, 150–62. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-64984-5_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Prins, Christian. "Chapter 7: The Capacitated Arc Routing Problem: Heuristics." In Arc Routing, 131–57. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611973679.ch7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Muyldermans, Luc, and Gu Pang. "Chapter 10: Variants of the Capacitated Arc Routing Problem." In Arc Routing, 223–53. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611973679.ch10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Belenguer, José Manuel, Enrique Benavent, and Stefan Irnich. "Chapter 9: The Capacitated Arc Routing Problem: Exact Algorithms." In Arc Routing, 183–221. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611973679.ch9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Lacomme, P., C. Prins, and M. Sevaux. "Multiobjective Capacitated Arc Routing Problem." In Lecture Notes in Computer Science, 550–64. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-36970-8_39.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ahr, Dino, and Gerhard Reinelt. "Chapter 8: The Capacitated Arc Routing Problem: Combinatorial Lower Bounds." In Arc Routing, 159–81. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611973679.ch8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Mei, Yi, Ke Tang, and Xin Yao. "Evolutionary Computation for Dynamic Capacitated Arc Routing Problem." In Studies in Computational Intelligence, 377–401. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38416-5_15.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Saruwatari, Yasufumi, Ryuichi Hirabayashi, and Naonori Nishida. "Subtour Elimination Algorithm for the Capacitated Arc Routing Problem." In Operations Research Proceedings, 334–41. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/978-3-642-77254-2_37.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Uncertain Capacitated Arc Routing Problem"

1

Mei, Yi, Ke Tang, and Xin Yao. "Capacitated arc routing problem in uncertain environments." In 2010 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2010. http://dx.doi.org/10.1109/cec.2010.5586031.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

MacLachlan, Jordan, and Yi Mei. "Look-Ahead Genetic Programming for Uncertain Capacitated Arc Routing Problem." In 2021 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2021. http://dx.doi.org/10.1109/cec45853.2021.9504785.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Wang, Juan, Ke Tang, and Xin Yao. "A memetic algorithm for uncertain Capacitated Arc Routing Problems." In 2013 IEEE Workshop on Memetic Computing (MC). IEEE, 2013. http://dx.doi.org/10.1109/mc.2013.6608210.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Wang, Shaolin, Yi Mei, and Mengjie Zhang. "Novel ensemble genetic programming hyper-heuristics for uncertain capacitated arc routing problem." In GECCO '19: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2019. http://dx.doi.org/10.1145/3321707.3321797.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Mei, Yi, and Mengjie Zhang. "Genetic programming hyper-heuristic for multi-vehicle uncertain capacitated arc routing problem." In GECCO '18: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2018. http://dx.doi.org/10.1145/3205651.3205661.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Wang, Shaolin, Yi Mei, John Park, and Mengjie Zhang. "Evolving Ensembles of Routing Policies using Genetic Programming for Uncertain Capacitated Arc Routing Problem." In 2019 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2019. http://dx.doi.org/10.1109/ssci44817.2019.9002749.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Ardeh, Mazhar Ansari, Yi Mei, and Mengjie Zhang. "Genetic programming hyper-heuristic with knowledge transfer for uncertain capacitated arc routing problem." In GECCO '19: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2019. http://dx.doi.org/10.1145/3319619.3321988.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ardeh, Mazhar Ansari, Yi Mei, and Mengjie Zhang. "A novel multi-task genetic programming approach to uncertain capacitated Arc routing problem." In GECCO '21: Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3449639.3459322.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Wang, Shaolin, Yi Mei, John Park, and Mengjie Zhang. "A Two-Stage Genetic Programming Hyper-Heuristic for Uncertain Capacitated Arc Routing Problem." In 2019 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2019. http://dx.doi.org/10.1109/ssci44817.2019.9002912.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Ardeh, Mazhar Ansari, Yi Mei, and Mengjie Zhang. "A GPHH with Surrogate-assisted Knowledge Transfer for Uncertain Capacitated Arc Routing Problem." In 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2020. http://dx.doi.org/10.1109/ssci47803.2020.9308398.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Uncertain Capacitated Arc Routing Problem' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography