Comparative Study of Emergency Logistics Path Planning

As natural disasters attract extensive attention worldwide,it is significant for governments and researchers to determine how to deliver emergency supplies after natural disasters.Considering the disaster victims' urgent needs for supplies after the disaster,based on the previous research,the path planning model from the shortest path and the optimal time was created in this paper.As in the actual road the outbreak of emergencies might cause some secondary disasters,including landslides triggered by heavy rain,paralysis of traffic together with a large crowd caused by earthquakes,the theory and method of the complex network to explore the topological structure characteristics of the whole network in the affected area were applied.Then,combining with the actual situation of the road network,the reliability analysis of the points,edges as well as topological structures were presented and a mathematical model based on reliability was proposed.Finally,two kinds of emergency logistics path planning models were compared and analyzed by some examples.The results showed that the relationship between time optimality and reliability was relevant.Emergency logistics path planning should not only consider the optimal transportation time of emergency logistics,but also pay attention to the reliability of transportation from a global perspective.

Competitive and Cooperative-Based Strength Pareto Evolutionary Algorithm for Green Distributed Heterogeneous Flow Shop Scheduling

This work aims to resolve the distributed heterogeneous permutation flow shop scheduling problem(DHPFSP)with minimizing makespan and total energy consumption(TEC).To solve this NP-hard problem,this work proposed a competitive and cooperative-based strength Pareto evolutionary algorithm(CCSPEA)which contains the following features:1)An initialization based on three heuristic rules is developed to generate a population with great diversity and convergence.2)A comprehensive metric combining convergence and diversity metrics is used to better represent the heuristic information of a solution.3)A competitive selection is designed which divides the population into a winner and a loser swarms based on the comprehensive metric.4)A cooperative evolutionary schema is proposed for winner and loser swarms to accelerate the convergence of global search.5)Five local search strategies based on problem knowledge are designed to improve convergence.6)Aproblem-based energy-saving strategy is presented to reduce TEC.Finally,to evaluate the performance of CCSPEA,it is compared to four state-of-art and run on 22 instances based on the Taillard benchmark.The numerical experiment results demonstrate that 1)the proposed comprehensive metric can efficiently represent the heuristic information of each solution to help the later step divide the population.2)The global search based on the competitive and cooperative schema can accelerate loser solutions convergence and further improve the winner’s exploration.3)The problembased initialization,local search,and energy-saving strategies can efficiently reduce the makespan and TEC.4)The proposed CCSPEA is superior to the state-of-art for solving DHPFSP.

Adaptive and augmented active anomaly detection on dynamic network traffic streams

Active anomaly detection queries labels of sampled instances and uses them to incrementally update the detection model,and has been widely adopted in detecting network attacks.However,existing methods cannot achieve desirable performance on dynamic network traffic streams because(1)their query strategies cannot sample informative instances to make the detection model adapt to the evolving stream and(2)their model updating relies on limited query instances only and fails to leverage the enormous unlabeled instances on streams.To address these issues,we propose an active tree based model,adaptive and augmented active prior-knowledge forest(A3PF),for anomaly detection on network trafic streams.A prior-knowledge forest is constructed using prior knowledge of network attacks to find feature subspaces that better distinguish network anomalies from normal traffic.On one hand,to make the model adapt to the evolving stream,a novel adaptive query strategy is designed to sample informative instances from two aspects:the changes in dynamic data distribution and the uncertainty of anomalies.On the other hand,based on the similarity of instances in the neighborhood,we devise an augmented update method to generate pseudo labels for the unlabeled neighbors of query instances,which enables usage of the enormous unlabeled instances during model updating.Extensive experiments on two benchmarks,CIC-IDS2017 and UNSW-NB15,demonstrate that A3PF achieves significant improvements over previous active methods in terms of the area under the receiver operating characteristic curve(AUC-ROC)(20.9%and 21.5%)and the area under the precision-recall curve(AUC-PR)(44.6%and 64.1%).

Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time

In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.

Balance Resource Allocation for Spark Jobs Based on Prediction of the Optimal Resource

Apache Spark provides a well-known Map Reduce computing framework,aiming to fast-process big data analytics in data-parallel manners.With this platform,large input data are divided into data partitions.Each data partition is processed by multiple computation tasks concurrently.Outputs of these computation tasks are transferred among multiple computers via the network.However,such a distributed computing framework suffers from system overheads,inevitably caused by communication and disk I/O operations.System overheads take up a large proportion of the Job Completion Time(JCT).We observed that excessive computational resources incurs considerable system overheads,prolonging the JCT.The over-allocation of individual jobs not only prolongs their own JCTs,but also likely makes other jobs suffer from under-allocation.Thus,the average JCT is suboptimal,too.To address this problem,we propose a prediction model to estimate the changing JCT of a single Spark job.With the support of the prediction method,we designed a heuristic algorithm to balance the resource allocation of multiple Spark jobs,aiming to minimize the average JCT in multiple-job cases.We implemented the prediction model and resource allocation method in Re B,a Resource-Balancer based on Apache Spark.Experimental results showed that Re B significantly outperformed the traditional max-min fairness and shortest-job-optimal methods.The average JCT was decreased by around 10%–30%compared to the existing solutions.

ADAPTIVE CGF COMMANDER BEHAVIOR MODELING THROUGH HTN GUIDED MONTE CARLO TREE SEARCH

Improving the intelligence of virtual entities is an important issue in Computer Generated Forces （CGFs） construction. Some traditional approaches try to achieve this by specifying how entities should react to predefined conditions, which is not suitable for complex and dynamic environments. This paper aims to apply Monte Carlo Tree Search （MCTS） for the behavior modeling of CGF commander. By look-ahead reasoning, the model generates adaptive decisions to direct the whole troops to fight. Our main work is to formulate the tree model through the state and action abstraction, and extend its expansion process to handle simultaneous and durative moves. We also employ Hierarchical Task Network （HTN） planning to guide the search, thus enhancing the search efficiency. The final implementation is tested in an infantry combat simulation where a company commander needs to control three platoons to assault and clear enemies within defined areas. Comparative results from a series of experiments demonstrate that the HTN guided MCTS commander can outperform other commanders following fixed strategies.

A Survey on Task and Participant Matching in Mobile Crowd Sensing

Mobile crowd sensing is an innovative paradigm which leverages the crowd, i.e., a large group of people with their mobile devices, to sense various information in the physical world. With the help of sensed information, many tasks can be fulfilled in an efficient manner, such as environment monitoring, traffic prediction, and indoor localization. Task and participant matching is an important issue in mobile crowd sensing, because it determines the quality and efficiency of a mobile crowd sensing task. Hence, numerous matching strategies have been proposed in recent research work. This survey aims to provide an up-to-date view on this topic. We propose a research framework for the matching problem in this paper, including participant model, task model, and solution design. The participant model is made up of three kinds of participant characters, i.e., attributes, requirements, and supplements. The task models are separated according to application backgrounds and objective functions. Offline and online solutions in recent literatures are both discussed. Some open issues are introduced, including matching strategy for heterogeneous tasks, context-aware matching, online strategy, and leveraging historical data to finish new tasks.

QoS-aware simulation job scheduling algorithm in virtualized cloud environment

Cloud computing is attracting an increasing number of simulation applications running in the virtualized cloud data center.These applications are submitted to the cloud in the form of simulation jobs.Meanwhile,the management and scheduling of simulation jobs are playing an essential role to offer efficient and high productivity computational service.In this paper,we design a management and scheduling service framework for simulation jobs in two-tier virtualization-based private cloud data center,named simulation execution as a service(SimEaaS).It aims at releasing users from complex simulation running settings,while guaranteeing the QoS requirements adaptively.Furthermore,a novel job scheduling algorithm named adaptive deadline-aware job size adjustment(ADaSA)algorithm is designed to realize high job responsiveness under QoS requirement for SimEaaS.ADaSA tries to make full use of the idle fragmentation resources by tuning the number of requested processes of submitted jobs in the queue adaptively,while guaranteeing that jobs’deadline requirements are not violated.Extensive experiments with trace-driven simulation are conducted to evaluate the performance of our ADaSA.The results show that ADaSA outperforms both cloud-based job scheduling algorithm KCEASY and traditional EASY in terms of response time(up to 90%)and bounded slow down(up to 95%),while obtains approximately equivalent deadline-missed rate.ADaSA also outperforms two representative moldable scheduling algorithms in terms of deadline-missed rate(up to 60%).