`Adaptive Link Adjustment' Applied to the Fixed Charge Transportation Problem

Sang-Moon SOAK

doi:10.1093/ietfec/e90-a.12.2863

`Adaptive Link Adjustment' Applied to the Fixed Charge Transportation Problem

Sang-Moon SOAK

Full Text Views

0

Share
Cite this

Summary :

The fixed charge transportation problem (FCTP) is a classic challenge for combinatorial optimization; it is based on the well-known transportation problem (TP), and is one of the prime examples of an NP-complete variant of the TP, of general importance in a wide range of transportation network design problems. Many techniques have been applied to this problem, and the most effective so far (in terms of near-optimal results in reasonable time on large instances) are evolutionary algorithm based approaches. In particular, an EA proposed by Eckert and Gottlieb has produced the best performance so far on a set of specific benchmark instances. We introduce a new scheme, which has more general applicability, but which we test here on the FCTP. The proposed scheme applies an adaptive mutation process immediately following the evaluation of a phenotype. It thereby adapts automatically to learned information encoded in the chromosome. The underlying encoding approach is to encode an ordering of elements for interpretation by a constructive algorithm (such as with the Link and Node Biased encoding for spanning trees, and the Random Keys encoding which has been applied to both scheduling and graph problems), however the main adaptive process rewards links in such a way that genes effectively encode a measure of the number of times their associated link has appeared in selected solutions. Tests are done which compare our approach with Eckert and Gottlieb's results on benchmark FCTP instances, and other approaches.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.12 pp.2863-2876

Publication Date: 2007/12/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e90-a.12.2863

Type of Manuscript: PAPER

Category: Numerical Analysis and Optimization

Cite this

Copy

Sang-Moon SOAK, "`Adaptive Link Adjustment' Applied to the Fixed Charge Transportation Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E90-A, no. 12, pp. 2863-2876, December 2007, doi: 10.1093/ietfec/e90-a.12.2863.
Abstract: The fixed charge transportation problem (FCTP) is a classic challenge for combinatorial optimization; it is based on the well-known transportation problem (TP), and is one of the prime examples of an NP-complete variant of the TP, of general importance in a wide range of transportation network design problems. Many techniques have been applied to this problem, and the most effective so far (in terms of near-optimal results in reasonable time on large instances) are evolutionary algorithm based approaches. In particular, an EA proposed by Eckert and Gottlieb has produced the best performance so far on a set of specific benchmark instances. We introduce a new scheme, which has more general applicability, but which we test here on the FCTP. The proposed scheme applies an adaptive mutation process immediately following the evaluation of a phenotype. It thereby adapts automatically to learned information encoded in the chromosome. The underlying encoding approach is to encode an ordering of elements for interpretation by a constructive algorithm (such as with the Link and Node Biased encoding for spanning trees, and the Random Keys encoding which has been applied to both scheduling and graph problems), however the main adaptive process rewards links in such a way that genes effectively encode a measure of the number of times their associated link has appeared in selected solutions. Tests are done which compare our approach with Eckert and Gottlieb's results on benchmark FCTP instances, and other approaches.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.12.2863/_p

Copy

@ARTICLE{e90-a_12_2863,
author={Sang-Moon SOAK, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={`Adaptive Link Adjustment' Applied to the Fixed Charge Transportation Problem},
year={2007},
volume={E90-A},
number={12},
pages={2863-2876},
abstract={The fixed charge transportation problem (FCTP) is a classic challenge for combinatorial optimization; it is based on the well-known transportation problem (TP), and is one of the prime examples of an NP-complete variant of the TP, of general importance in a wide range of transportation network design problems. Many techniques have been applied to this problem, and the most effective so far (in terms of near-optimal results in reasonable time on large instances) are evolutionary algorithm based approaches. In particular, an EA proposed by Eckert and Gottlieb has produced the best performance so far on a set of specific benchmark instances. We introduce a new scheme, which has more general applicability, but which we test here on the FCTP. The proposed scheme applies an adaptive mutation process immediately following the evaluation of a phenotype. It thereby adapts automatically to learned information encoded in the chromosome. The underlying encoding approach is to encode an ordering of elements for interpretation by a constructive algorithm (such as with the Link and Node Biased encoding for spanning trees, and the Random Keys encoding which has been applied to both scheduling and graph problems), however the main adaptive process rewards links in such a way that genes effectively encode a measure of the number of times their associated link has appeared in selected solutions. Tests are done which compare our approach with Eckert and Gottlieb's results on benchmark FCTP instances, and other approaches.},
keywords={},
doi={10.1093/ietfec/e90-a.12.2863},
ISSN={1745-1337},
month={December},}

Copy

TY - JOUR
TI - `Adaptive Link Adjustment' Applied to the Fixed Charge Transportation Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2863
EP - 2876
AU - Sang-Moon SOAK
PY - 2007
DO - 10.1093/ietfec/e90-a.12.2863
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2007
AB - The fixed charge transportation problem (FCTP) is a classic challenge for combinatorial optimization; it is based on the well-known transportation problem (TP), and is one of the prime examples of an NP-complete variant of the TP, of general importance in a wide range of transportation network design problems. Many techniques have been applied to this problem, and the most effective so far (in terms of near-optimal results in reasonable time on large instances) are evolutionary algorithm based approaches. In particular, an EA proposed by Eckert and Gottlieb has produced the best performance so far on a set of specific benchmark instances. We introduce a new scheme, which has more general applicability, but which we test here on the FCTP. The proposed scheme applies an adaptive mutation process immediately following the evaluation of a phenotype. It thereby adapts automatically to learned information encoded in the chromosome. The underlying encoding approach is to encode an ordering of elements for interpretation by a constructive algorithm (such as with the Link and Node Biased encoding for spanning trees, and the Random Keys encoding which has been applied to both scheduling and graph problems), however the main adaptive process rewards links in such a way that genes effectively encode a measure of the number of times their associated link has appeared in selected solutions. Tests are done which compare our approach with Eckert and Gottlieb's results on benchmark FCTP instances, and other approaches.
ER -