Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window
Yan LI, Dazhi PAN, Siqing ZHENG
Journal of Computer Applications    2024, 44 (6): 1897-1904.   DOI: 10.11772/j.issn.1001-9081.2023060760
Abstract199)   HTML12)    PDF (2184KB)(121)       Save

Aiming at the Multi-Depot Vehicle Routing Problem with Time Window (MDVRPTW), an Improved Adaptive Large Neighborhood Search algorithm (IALNS) was proposed. Firstly, a path segmentation algorithm was improved in the stage of constructing the initial solution. Then, in the optimization stage, the designed removal and repair heuristic operators were used to compete with each other to select the optimal operator, a scoring mechanism was introduced for the operators, and the heuristic operator was selected by roulette. At the same time, the iteration cycle was segmented and the operator weight information was dynamically adjusted in each cycle, effectively to prevent the algorithm from falling into local optimum. Finally, simulated annealing mechanism was adopted as the acceptance criterion of the solution. The relevant parameters of the IALNS were determined by experiments on the Cordeau normative instances, and the solution results of the proposed algorithm were compared with other representative research results in this field. The experimental results show that the solution error between IALNS and Variable Neighborhood Search (VNS) algorithm does not exceed 0.8%, even better in some cases; compared with the multi-phase improved shuffled frog leaping algorithm, the average time-consuming of the proposed algorithm is reduced by 12.8%, and the runtime is shorter for most instances. So the above results verify IALNS is an effective algorithm for solving MDVRPTW.

Table and Figures | Reference | Related Articles | Metrics
Lightweight algorithm of 3D mesh model for preserving detailed geometric features
Yun ZHANG, Shuying WANG, Qing ZHENG, Haizhu ZHANG
Journal of Computer Applications    2023, 43 (4): 1226-1232.   DOI: 10.11772/j.issn.1001-9081.2022030434
Abstract461)   HTML12)    PDF (3119KB)(274)       Save

An important strategy for lightweighting a 3D model is to use the mesh simplification algorithm to reduce the number of triangular meshes on the model surface. The widely used edge collapse algorithm is more efficient and has better simplification effect than other mesh simplification algorithms, but some detailed geometric features may be damaged or lost during the simplification process of this algorithm. Therefore, the approximate curvature of curve and the average area of the first-order neighborhood triangle of the edge to be collapsed were added as penalty factors to optimize the edge collapse cost of the original algorithm. First, according to the definition of curve curvature in geometry, the calculation formula of the approximate curvature of curve was proposed. Then, in the calculation process of vertex normal vector, two stages - area weighting and interior angle weighting were used to modify the initial normal vector, thereby considering more abundant geometric information of the model. The performance of the optimized algorithm was verified by experiments. Compared with the classical Quadratic Error Metric (QEM) algorithm and the mesh simplification algorithm considering the angle error, the optimized algorithm has the maximum error reduced by 73.96% and 49.77% at least and respectively. Compared with the QEM algorithm, the optimized algorithm has the Hausdorff distance reduced by 17.69% at least. It can be seen that in the process of model lightweighting, the optimized algorithm can reduce the deformation of the model and better maintain its own detailed geometric features.

Table and Figures | Reference | Related Articles | Metrics
Low-cost RFID authentication protocol based on PUF
HE Zhang-qing ZHENG Zhao-xia DAI Kui ZOU Xue-cheng
Journal of Computer Applications    2012, 32 (03): 683-685.   DOI: 10.3724/SP.J.1087.2012.00683
Abstract1735)      PDF (687KB)(741)       Save
The available security mechanisms for the low-cost Radio Frequency IDentification (RFID) systems are either defective or high-cost. Therefore, this paper proposed an efficient security authentication protocol for low-cost RFID system based on Physical Unclonable Function (PUF) and Linear Feedback Shift Register (LFSR). The protocol provides strong security and can resist physical attack and tag clone with strong privacy.
Reference | Related Articles | Metrics
Joint precoding scheme under condition of channel asymmetry
Li-qing ZHENG Kai-zhi HUANG Yin-hai LI
Journal of Computer Applications    2011, 31 (08): 2025-2028.   DOI: 10.3724/SP.J.1087.2011.02025
Abstract1436)      PDF (614KB)(983)       Save
In a Base Station (BS) cooperation system, the capacity gains of two BSs by cooperating with each other are different owing to the channel asymmetry. Thus, in the process of selecting cooperative BS, when one BS wants to coordinate but another does not want to cooperate with it and prefers others, it will be difficult to judge whether to group the two into a cluster or not and the whole system is capacity-limited. To demonstrate this, the authors proposed an overlapped clustering scheme and then designed a joint precoding algorithm called Zero Force-Tomlinson-Harashima Precoding (ZF-THP) scheme. In this scheme, several BSs were adjusted to be overlapped and THP technique was used to eliminate the interference caused by overlapped BSs. The simulation results show that the proposed scheme solves the clustering contradiction well, efficiently increases the system capacity and enhances the system fairness.
Reference | Related Articles | Metrics